✨Tìm kiếm tuần tự

Trong Khoa học máy tính tìm kiếm tuần tự (tiếng Anh Sequential search) hay tìm kiếm tuyến tính (tiếng Anh linear search) là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến lúc tìm thấy giá trị mong muốn hay đã duyệt qua toàn bộ danh sách.

Ứng dụng

Tìm kiếm tuần tự là một giải thuật rất đơn giản khi hiện thực. Giải thuật này tỏ ra khá hiệu quả khi cần tìm kiếm trên một danh sách đủ nhỏ hoặc một danh sách chưa sắp thứ tự đơn giản. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được xử lý một lần trước khi tìm kiếm: có thể được sắp xếp theo thứ tự, hoặc được xây dựng theo một cấu trúc dữ liệu đặc trưng cho giải thuật hiệu quả hơn,...

Mã giả

Phiên bản lặp tự nhiên

Đây là phiên bản hay gặp nhất của giải thuật này, kết quả trả về sẽ là vị trí của phần tử cần tìm hoặc một giá trị Δ thể hiện việc không tìm thấy phần tử trong danh sách đó.

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

Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử cần tìm có thể là chỉ số của nó trong mảng, còn giá trị Δ có thể là chỉ số nằm trước phần tử đầu tien (0 hoặc -1 tùy vào danh sách).

Nếu danh sách là một danh sách liên kết, vị trí của phần tử được trả về có thể nằm dưới dạng địa chỉ của no, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

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

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. search the value in the remainder of the list, and return the result.

Sử dụng phần tử cầm canh

Một phương pháp được sử dụng để cải thiện hiệu quả của giải thuật là chèn phần tử muốn tìm kiếm và cuối danh sách như một phần tử cầm canh (sentinel) như được trình bày dưới đây:

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

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử dụng khi vị trí cuối cùng của danh sách tồn tại nhưng chưa được sử dụng.

Tìm kiếm tuần tự trên một danh sách đã sắp xếp

Trong các danh sách đã được sắp xếp nhưng bắt buộc phải truy xuất tuần tự như danh sách liên kết hay tệp tin, việc tìm kiếm tuần tự sẽ hiệu quả hơn trong nhiều trường hợp không cần duyệt toàn bộ danh sách vẫn kết luận được phần tử đó không có mặt. Tuy nhiên, với một mảng được sắp xếp, việc tìm kiếm nhị phân tỏ ra hiệu quả trong đa số trường hợp