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 tòi ở cuối list hoặc không tồn tại nhập danh sách
Thời gian tham 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 tòi một thành phần cho tới trước nhập một list bằng phương pháp duyệt theo lần lượ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 chuyện 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 rất rất giản dị và đơn giản khi một cách 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 tòi 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 tòi rất nhiều lần, tài liệu thông thường được xử lý một lượ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 xây đắp theo đòi một cấu hình tài liệu đặc thù cho tớ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 gặp gỡ nhất của giải thuật này, Search Engine Results Page đượ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 kiếm thấy thành phần nhập 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ó nhập 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 nhập danh sách).

Xem thêm: hoán dụ và ẩn dụ

Nếu list là một trong những list links, đị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 một cách thực tế giải thuật mò mẫm tìm tòi tuần tự động.

Xem thêm: văn mẫu chiếc thuyền ngoài xa

 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ầm canh[sửa | sửa mã nguồn]

Một cách thức được dùng nhằm nâng cấp hiệu suất cao của giải thuật là chèn thành phần ham muốn mò mẫm tìm tòi và cuối list như 1 thành phần cầm 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ầm canh gom giảm sút việc đối chiếu chỉ số thời điểm hiện tại 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 sau 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 sẽ phải truy xuất tuần tự động như list links hoặc tệp tin cẩn, việc mò mẫm tìm tòi 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 tòi nhị phân trầm trồ hiệu suất cao nhập phần lớn ngôi trường hợp