Thuật toán tìm kiếm tuyến tính (Linear Search)

1. Giải thuật

Tìm kiếm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Các bước tiến hành như sau:

Bước 1: i = 1;// Bắt đầu phần tử đầu tiên của dãy
Bước 2: So sánh a[i] với x, có 2 khả năng:
 + a[i] = x: Tìm thấy. Dừng
 +a[i] khác x: Sang bước 3.
Bước 3: i = i+1; //xét phần tử kế tiếp trong mảng
Nếu i>N: Hết mảng, không tìm thấy. Dừng
Ngược lại: Lặp lại Bước 2.

2. Cài đặt
Từ mô tả trên của thuật toán tìm kiếm tuyến tính, có thể cài đặt hàm LinearSearch để xác định vị trí của phần tử có khóa x trong mảng a:

Mã ngôn ngữ C

CODE:

int LinearSearch(int a[], int N, int x){ int i = 0; while ((i < N) && (a[i] != x)) i++; if (i == N) return -1; //tìm hết mảng nhưng không có x else return i;// a[i] là phần tử có khóa x}

Trong cài đặt trên đây, nhận thấy mỗi lần lặp của vòng lặp while phải tiến hành kiểm tra 2 điều kiện (i<N) - điều kiện biên của mảng - và (a[i] != x) - điều kiện kiểm tra chính. Nhưng thật sự chỉ cần kiểm tra điều kiện chính (a[i] != x) , để cải tiến cài đặt có thể dùng phương pháp "lính canh" - đặt thêm 1 phần tử có giá trị x vào cuối mảng, như vậy bảo đảm luôn tìm thấy x trong mảng, sau đó dưạ vào vị trí tìm thấy để kết luận. Cài đặt cải tiến sau đây của hàm LinearSearch giúp giảm bớt một phép so sánh trong vòng lặp:

Mã ngôn ngữ C

CODE:


int LinearSearch(int a[], int N, int x){ int i = 0; //mảng gồm N phần tử từ a[0]...a[N-1] a[N] = x; //thêm phần tử thứ N+1 while (a[i] != x) i++; if (i == N) return -1; //tìm hết mảng nhưng không có x else return i; //tìm thấy x tại vị trí i}

3. Đánh giá giải thuật
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm kiếm tuyến tính, có:

Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n).

4. Nhận xét
   * Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
  * Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.

[BinarySearch] Thuật toán tìm kiếm nhị phân
[Demo đồ họa] Thuật toán tìm kiếm