Linear Search - Tìm Kiếm Tuyến Tính

Linear Search

Linear search có các tên gọi khác như Sequential search – Tìm kiếm tuần tự  – Tìm kiếm tuyến tính là 1 trong các giải thuật hỗ trợ tìm kiếm 1 phần tử trong mảng.

Ý tưởng

Tìm kiếm từ đầu cho đến cuối mảng (hoặc ngược lại).

• Nếu tìm thấy trả vị trí của kết quả tìm kiếm.
• Nếu không tìm thấy thì trả về 1.

Code mẫu Linear Search

#include <iostream>
using namespace std;

int LinearSearch(int arr[], int numberOfElements, int key)
{
    for (int i = 0; i < numberOfElements; i++)
        if (arr[i] == key)
            return i;
    return -1;
}

int main()
{
    int arr[] = { 10, 8, 1, 21, 7, 32, 5, 11, 0 };
    int size = sizeof(arr) / sizeof(arr[0]);

    int index = LinearSearch(arr, size, 5);

    if (index == -1)
        cout << "Khong tim thay!" << endl;
    else
        cout << "Vi tri tim thay la: " << index << endl;

    return 0;
}

Output: Vi tri tim thay la: 6.

Các bước thực hiện

• Bước 1: Duyệt mảng từ vị trí đầu tiên i = 0.
• Bước 2: Thực hiện so sánh arr[i] và key. Nếu arr[i] == key trả về vị trí i.
  • Trong trường hợp này hàm sẽ trả về giá trị i = 6 do 7 nằm ở vị trí thứ 6.
• Bước 3: Nếu duyệt hết mảng vẫn không tìm thấy thì trả về -1.

Đánh giá

• Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
• Trong trường hợp xấu nhất, phần tử cần tìm nằm ở vị trí cuối hoặc không nằm trong mảng, thuật toán sử dụng n - 1 lần so sánh.
• Linear Search là một giải thuật đơn giản khi hiện thực và khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp.