Tìm kiếm nhị phân

Khi danh sách được sắp xếp, chúng ta có thể sử dụng kỹ thuật tìm kiếm nhị phân để tìm các mục trong danh sách. Trong thủ tục này, toàn bộ danh sách được chia thành hai danh sách con. Nếu mục được tìm thấy ở vị trí chính giữa, nó sẽ trả về vị trí, nếu không sẽ chuyển sang danh sách phụ bên trái hoặc bên phải và thực hiện lại quy trình tương tự cho đến khi tìm thấy mục hoặc vượt quá phạm vi.

Sự phức tạp của Kỹ thuật Tìm kiếm Nhị phân

• Độ phức tạp về thời gian : O (1) cho trường hợp tốt nhất. O (log2 n) cho trường hợp trung bình hoặc xấu nhất.
• Mức độ phức tạp của không gian: O (1)

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

Input: 
A sorted list of data: 12 25 48 52 67 79 88 93
The search key 79
Output:
Item found at location: 5

Thuật toán

binarySearch(array, start, end, key)

Đầu vào - Một mảng được sắp xếp, vị trí bắt đầu và kết thúc, và phím 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
   if start <= end then
      mid := start + (end - start) /2
      if array[mid] = key then
         return mid location
      if array[mid] > key then
         call binarySearch(array, mid+1, end, key)
      else when array[mid] < key then
         call binarySearch(array, start, mid-1, key)
   else
      return invalid location
End

Ví dụ

#include<iostream>
using namespace std;

int binarySearch(int array[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

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 = binarySearch(arr, 0, 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:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 79
Item found at location: 5