Tìm kiếm nhị phân (Binary Search) - Thuật toán hiệu quả cho mảng đã sắp xếp

Khi danh sách đã sắp xếp, Binary Search chia danh sách thành 2 nửa. Nếu khóa ở giữa -> trả về. Nếu không, chuyển sang nửa trái hoặc phải và lặp lại.

Độ phức tạp

• Thời gian: Best O(1), Avg/Worst O(log₂ n)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  Sorted: 12 25 48 52 67 79 88 93, key=79
Output: Item found at location: 5

Thuật toán

binarySearch(array, start, end, key)
Begin
    if start <= end:
        mid = start + (end - start) / 2
        if array[mid] == key: return mid
        if array[mid] > key: return binarySearch(array, start, mid-1, key)
        else: return binarySearch(array, mid+1, end, key)
    else: return invalid location
End

Ví dụ C++

#include <iostream>
using namespace std;

int binarySearch(int arr[], int s, int e, int key) {
    if(s<=e) {
        int mid = s + (e-s)/2;
        if(arr[mid]==key) return mid;
        if(arr[mid] > key) return binarySearch(arr, s, mid-1, key);
        return binarySearch(arr, mid+1, e, key);
    }
    return -1;
}

int main() {
    int n, key, loc;
    cout << "Enter number of items: "; cin >> n;
    int arr[n]; cout << "Enter items: " << endl;
    for(int i=0;i> arr[i];
    cout << "Enter search key: "; cin >> key;
    if((loc=binarySearch(arr,0,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: 12 25 48 52 67 79 88 93
Enter search key: 79
Item found at location: 5