Tìm kiếm tuyến tính

Kỹ thuật tìm kiếm tuyến tính là kỹ thuật đơn giản nhất. Trong kỹ thuật này, các mục được tìm kiếm từng cái một. Quy trình này cũng có thể áp dụng cho tập dữ liệu chưa được sắp xếp. Tìm kiếm tuyến tính còn được gọi là tìm kiếm tuần tự. Nó được đặt tên là tuyến tính vì độ phức tạp thời gian của nó có bậc là n O (n).

Sự phức tạp của Kỹ thuật Tìm kiếm Tuyến tính

• Độ phức tạp về thời gian: O (n)
• Mức độ phức tạp của không gian: O (1)

Đầu vào và Đầu ra

Input:
A list of data:
20 4 89 75 10 23 45 69
the search key 10
Output:
Item found at location: 4

Thuật toán

linearSearch(array, size, key)

Đầu vào - Mảng được sắp xếp, kích thước của mảng và khóa tìm kiếm

Đầu ra - vị trí của chìa khóa (nếu được tìm thấy), nếu không thì sai vị trí.

Begin
   for i := 0 to size -1 do
      if array[i] = key then
         return i
   done
   return invalid location
End

Ví dụ

#include<iostream>
using namespace std;

int linSearch(int array[], int size, int key) {
   for(int i = 0; i<size; i++) {
      if(array[i] == key) //search key in each places of the array
         return i; //location where key is found for the first time
   }
   return -1; //when the key is not in the list
}

int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; //create an array of size n
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter search key to search in the list: ";
   cin >> searchKey;

   if((loc = linSearch(arr, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Đầu ra

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