Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm tuần tự (Sequential/Linear search)

[Quoc_Khanh_Tran (Quốc Khánh Trần)]

Giải thuật tìm kiếm tuần tự (Sequential/Linear search)

Thuật toán này tìm kiếm 1 phần tử thuộc 1 tập hữu hạn bất kì (tập các số nguyên, tập các kí tự… nhưng ở đây là tập số nguyên). Phần tử cần tìm gọi là khóa tìm kiếm. Tập các số nguyên được biểu diễn bằng mảng 1 chiều (dãy).

1. Ý tưởng thuật toán

So sánh các phần tử thuộc dãy với khóa, bắt đầu từ đầu dãy, nếu:
- Không tìm thấy khóa: trả về 1 trị số nào đó (ví dụ -1).
- Tìm thấy khóa tại vị trí i: trả về giá trị i.

2. Các bước của thuật toán

Bước 1: i = 0 //duyệt từ đầu dãy
Bước 2: Khi chưa duyệt hết dãy (i < n), đồng thời chưa tìm thấy khóa x (a[i] != x) thì:
- Bước 2.1. Tìm ở vị trí tiếp theo (i++)
- Bước 2.2. Nếu hết dãy mà vẫn chưa thấy khóa x thì trả về -1 và kết thúc.
- Bước 2.3. Nếu thấy khóa tại vị trí i (a[i] = x) thì trả về i và kết thúc.

3. Cài đặt (C++)

int seq_search(int a[], int n, int x) {
    int i=0;
    while((i<n) && (a[i]!=x))
        i++;
    if(i==n) return -1; //Khong tim thay x
    else return i; //Tim thay x tai vi tri i
}

4. Độ phức tạp của thuật toán

Độ phức tạp của thuật toán được đánh giá thông qua số lượng các phép so sánh thực hiện suốt chiều dài của dãy để tìm khóa x. Các tình huống:

• Tốt nhất:
  Số lần so sánh: 1 (Tìm thấy khóa x ngay tại vị trí đầu tiên).
• Xấu nhất:
  Số lần so sánh: n (Duyệt hết dãy mới thấy khóa x).
• Trung bình:
  Số lần so sánh: n/2 (Duyệt đến giữa dãy thì thấy khóa x).

Độ phức tạp: O(n).