Tìm kiếm tuần tự

Trong Khoa học máy tính, tìm kiếm tuần tự (hay còn gọi là Sequential search) hoặc tìm kiếm tuyến tính (tiếng Anh linear search) là một phương pháp dò tìm một phần tử trong danh sách bằng cách kiểm tra từng phần tử một cho đến khi tìm thấy mục tiêu hoặc kiểm tra hết danh sách.

Ứng dụng

Tìm kiếm tuần tự là một thuật toán đơn giản và dễ thực hiện. Nó đặc biệt hiệu quả khi tìm kiếm trong danh sách nhỏ hoặc danh sách không được sắp xếp. Đối với các tìm kiếm nhiều lần, dữ liệu thường được chuẩn bị trước, chẳng hạn như sắp xếp hoặc tổ chức theo cấu trúc dữ liệu phù hợp để cải thiện hiệu suất.

Mã giả

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

Đây là kiểu giải thuật phổ biến nhất, trả về vị trí của phần tử cần tìm hoặc giá trị Δ nếu phần tử không có trong danh sách.

1. Duyệt qua từng phần tử trong danh sách:
     1. Nếu phần tử đó có giá trị mong muốn,
         1. Dừng tìm kiếm và trả về vị trí của phần tử.
 2. Trả về 'Δ' nếu không tìm thấy.

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ị Δ là chỉ số trước phần tử đầu tiên (0 hoặc -1 tùy theo danh sách).

Nếu danh sách là danh sách liên kết, vị trí của phần tử có thể là địa chỉ của nó, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

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

1. Nếu danh sách rỗng, trả về Λ;
 2. Ngược lại:
    1. Nếu phần tử đầu tiên có giá trị mong muốn,
       1. Trả về vị trí của nó;
    2. Nếu không,
       1. Tìm kiếm giá trị trong phần còn lại của danh sách và trả về kết quả.

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

Một cách để nâng cao hiệu quả giải thuật là thêm phần tử cần tìm vào cuối danh sách như một phần tử cầm canh (sentinel) như dưới đây:

1. Đặt A[n + 1] bằng x.
 2. Khởi tạo i bằng 1.
 3. Lặp lại vòng lặp này:
     1. Nếu A[i] = x,
        1. Thoát khỏi vòng lặp.
     2. Tăng i lên 1.
 4. Trả về i.

Việc thêm phần tử cầm canh giúp giảm số lần so sánh giữa chỉ số hiện tại i và số phần tử n trong mỗi vòng lặp. Tuy nhiên, phương pháp này chỉ khả dụng khi vị trí cuối cùng của danh sách đã được xác định nhưng chưa sử dụng.

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

Đối với danh sách đã được sắp xếp nhưng yêu cầu phải truy xuất tuần tự như danh sách liên kết hay tệp tin, tìm kiếm tuần tự có thể hiệu quả hơn trong nhiều trường hợp, giúp kết luận nhanh chóng rằng phần tử không có mặt mà không cần duyệt toàn bộ danh sách. Tuy nhiên, đối với mảng đã sắp xếp, tìm kiếm nhị phân thường hiệu quả hơn trong đa số tình huống.