Tìm kiếm tuần tự

Bách khoa toàn thư banh Wikipedia

Tìm mò mẫm tuần tự
Phân loại	giải thuật mò mẫm kiếm
Cấu trúc dữ liệu	danh sách
Độ phức tạp thời gian	O(n) Khi thành phần mò mẫm tìm kiếm ở cuối list hoặc không tồn tại vô danh sách
Thời gian trá chạy đảm bảo chất lượng nhất	O(1) Khi thành phần cần thiết mò mẫm nằm ở đầu danh sách
Độ phức tạp ko gian	O(n)

Trong Khoa học tập PC tìm mò mẫm tuần tự (tiếng Anh Sequential search) hoặc tìm mò mẫm tuyến tính (tiếng Anh linear search) là một trong những cách thức mò mẫm tìm kiếm một thành phần mang lại trước vô một list bằng phương pháp duyệt theo thứ tự từng thành phần của list cơ cho tới khi nhìn thấy độ quý hiếm mong ước hoặc tiếp tục duyệt qua loa toàn cỗ list.

Bạn đang xem: thuật toán tìm kiếm tuần tự

Ứng dụng[sửa | sửa mã nguồn]

Tìm mò mẫm tuần tự là một trong những giải thuật cực kỳ giản dị và đơn giản Khi thực tế. Giải thuật này trầm trồ khá hiệu suất cao Khi cần thiết mò mẫm tìm kiếm bên trên một list đầy đủ nhỏ hoặc một list ko chuẩn bị trật tự giản dị và đơn giản. Trong tình huống cần thiết mò mẫm tìm kiếm rất nhiều lần, tài liệu thông thường được xử lý một đợt trước lúc mò mẫm kiếm: hoàn toàn có thể được bố trí theo đòi trật tự, hoặc được kiến tạo theo đòi một cấu tạo tài liệu đặc thù mang lại giải thuật hiệu suất cao rộng lớn,...

Mã giả[sửa | sửa mã nguồn]

Phiên phiên bản lặp tự động nhiên[sửa | sửa mã nguồn]

Đây là phiên phiên bản hoặc bắt gặp nhất của giải thuật này, SERP được xem là địa điểm của thành phần cần thiết mò mẫm hoặc một độ quý hiếm Δ thể hiện tại việc không tìm kiếm thấy thành phần vô list cơ.

 1. For each item in the list:
     1. if that item has the desired value,
         1. stop the tìm kiếm and return the item's location.
 2. Return 'Δ

Nếu list được tàng trữ bên dưới dạng mảng, địa điểm của thành phần cần thiết mò mẫm hoàn toàn có thể là chỉ số của chính nó vô mảng, còn độ quý hiếm Δ hoàn toàn có thể là chỉ số ở trước thành phần đầu tien (0 hoặc -1 tùy vô danh sách).

Xem thêm: Ca Khia TV - Link phát sóng trực tiếp đá bóng chất lượng số 1

Nếu list là một trong những list link, địa điểm của thành phần được trả về hoàn toàn có thể ở bên dưới dạng địa điểm của no, còn độ quý hiếm Δ hoàn toàn có thể là độ quý hiếm null.

Phiên phiên bản đệ quy[sửa | sửa mã nguồn]

Đây là phiên phiên bản đệ quy Khi thực tế giải thuật mò mẫm tìm kiếm tuần tự động.

Xem thêm: enjoy + ving hay to v

 1. if the list is empty, return Λ;
 2. else
    1. if the first item of the list has the desired value
       1. return its location;
    2. else 
       1. tìm kiếm the value in the remainder of the list, and return the result.

Sử dụng thành phần cố canh[sửa | sửa mã nguồn]

Một cách thức được dùng nhằm nâng cao hiệu suất cao của giải thuật là chèn thành phần mong muốn mò mẫm tìm kiếm và cuối list như 1 thành phần cố canh (sentinel) như được trình diễn bên dưới đây:

 1. Set A[n + 1] to tát x. 
 2. Set i to tát 1.
 3. Repeat this loop:
     1. If A[i] = x, 
        1. exit the loop.
     2. Set i to tát i + 1.
 4. Return i.

Việc thêm thắt thành phần cố canh gom giảm sút việc đối chiếu chỉ số lúc này i với số những thành phần n ở từng vòng lặp. Tuy nhiên, điều này chỉ hoàn toàn có thể được dùng Khi địa điểm ở đầu cuối của list tồn bên trên tuy nhiên không được dùng.

Tìm mò mẫm tuần tự động bên trên một list tiếp tục chuẩn bị xếp[sửa | sửa mã nguồn]

Trong những list và đã được bố trí tuy nhiên cần phải truy xuất tuần tự động như list link hoặc tệp tin yêu, việc mò mẫm tìm kiếm tuần tự động tiếp tục hiệu suất cao rộng lớn trong không ít tình huống ko cần thiết duyệt toàn cỗ list vẫn Tóm lại được thành phần cơ ko xuất hiện. Tuy nhiên, với cùng một mảng được bố trí, việc mò mẫm tìm kiếm nhị phân trầm trồ hiệu suất cao vô số đông ngôi trường hợp