Tìm kiếm 지수 (Exponential Search) - Kết hợp nhảy và nhị phân

Exponential Search (còn gọi doubling/galloping search) dùng để tìm phạm vi chứa khóa. L và U là lũy thừa của 2. Sau khi tìm phạm vi, dùng binary search trong phạm vi đó.

Độ phức tạp

• Thời gian: Best O(1), Avg/Worst O(log₂ i) (i = vị trí khóa)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  Sorted: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995, key=780
Output: Item found at location: 16

Thuật toán

Binary Search (hàm phụ):

binarySearch(array, start, end, key)
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

Exponential Search:

exponentialSearch(array, start, end, key)
if (end-start) <= 0: return invalid
i := 1
while i < (end-start):
    if array[i] < key: i := i * 2
    else: break
done
return binarySearch(array, i/2, i, key)

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 exponentialSearch(int arr[], int s, int e, int key) {
    if(e-s <= 0) return -1;
    int i = 1;
    while(i < e-s) {
        if(arr[i] < key) i *= 2;
        else break;
    }
    return binarySearch(arr, i/2, i, key);
}

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=exponentialSearch(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: 20
Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key: 780
Item found at location: 16