Tìm kiếm tuyến tính (Linear Search) - Thuật toán đơn giản nhất

Tìm kiếm tuyến tính (Linear Search) là kỹ thuật đơn giản nhất. Duyệt từng phần tử một. Áp dụng được cho dữ liệu không sắp xếp. Còn gọi là sequential search. Tên "linear" vì độ phức tạp O(n).

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  List: 20 4 89 75 10 23 45 69, key=10
Output: Item found at location: 4

Thuật toán

linearSearch(array, size, key)
Begin
    for i = 0 to size-1:
        if array[i] == key: return i
    done
    return invalid location
End

Ví dụ C++

#include <iostream>
using namespace std;

int linSearch(int arr[], int n, int key) {
    for(int i=0;i> n;
    int arr[n]; cout << "Enter items: " << endl;
    for(int i=0;i> arr[i];
    cout << "Enter search key: "; cin >> key;
    if((loc=linSearch(arr,n,key))>=0) cout << "Item found at location: " << loc << endl;
    else cout << "Item not found." << endl;
}

Kết quả

Enter number of items: 8
Enter items: 20 4 89 75 10 23 45 69
Enter search key: 10
Item found at location: 4