Tìm kiếm nội suy (Interpolation Search) - Cải tiến Binary Search

Binary search chia đôi đều. Interpolation Search ước lượng vị trí khóa bằng công thức nội suy. Nếu dữ liệu phân bố đều, tìm nhanh hơn binary search.

Độ phức tạp

• Thời gian: Trung bình O(log₂(log₂ n)), xấu nhất O(n) (khi phân bố mũ)
• 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

interpolationSearch(array, start, end, key)
Begin
    while start <= end AND key >= array[start] AND key <= array[end]:
        dist     := key - array[start]
        valRange := array[end] - array[start]
        fraction := dist / valRange
        indexRange := end - start
        estimate := start + floor(fraction * indexRange)
        if array[estimate] == key: return estimate
        if array[estimate] < key: start := estimate + 1
        else: end := estimate - 1
    done
    return invalid position
End

Ví dụ C++

#include <iostream>
using namespace std;

int interpolationSearch(int arr[], int start, int end, int key) {
    int dist, valRange, indexRange, estimate;
    float fraction;
    while(start <= end && key >= arr[start] && key <= arr[end]) {
        dist = key - arr[start];
        valRange = arr[end] - arr[start];
        fraction = (float)dist / valRange;
        indexRange = end - start;
        estimate = start + (int)(fraction * indexRange);
        if(arr[estimate] == key) return estimate;
        if(arr[estimate] < key) start = estimate + 1;
        else end = estimate - 1;
    }
    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=interpolationSearch(arr,0,n-1,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