Chương trình C++ triển khai thuật toán tìm kiếm nội suy (Interpolation Search)

Đối với kỹ thuật tìm kiếm nhị phân, danh sách được chia thành các phần bằng nhau. Đối với kỹ thuật tìm kiếm nội suy (interpolation search), thủ tục sẽ cố gắng định vị vị trí chính xác bằng công thức nội suy. Sau khi tìm thấy vị trí ước lượng, nó có thể tách danh sách bằng vị trí đó. Vì nó cố gắng tìm vị trí chính xác mỗi lần, nên thời gian tìm kiếm giảm đi. Kỹ thuật này có thể tìm mục tiêu dễ dàng nếu các mục được phân phối đều.

Độ phức tạp của kỹ thuật Tìm kiếm nội suy

• Độ phức tạp thời gian: O(log₂(log₂ n)) cho trường hợp trung bình, và O(n) cho trường hợp xấu nhất (khi các mục phân phối theo cấp số nhân)
• Độ phức tạp không gian: O(1)

Đầu vào — Danh sách dữ liệu đã sắp xếp: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995. Khóa tìm kiếm: 780
Đầu ra — Mục tìm thấy tại vị trí: 16

Thuật toán

interpolationSearch(array, start, end, key)

Đầu vào: Mảng đã sắp xếp, vị trí bắt đầu và kết thúc, và khóa tìm kiếm

Đầu ra: Vị trí của khóa (nếu tìm thấy), ngược lại vị trí không hợp lệ.

Bắt đầu
    while start <= end VÀ key >= array[start] VÀ key <= array[end]
        dist := key – array[start]
        valRange := array[end] – array[start]
        fraction := dist / valRange
        indexRange := end – start
        estimate := start + (fraction * indexRange)
        if array[estimate] = key thì
            trả về vị trí estimate
        if array[estimate] < key thì
            start := estimate + 1
        else
            end = estimate - 1
    Trả về vị trí không hợp lệ
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

int interpolationSearch(int array[], int start, int end, int key) {
    int dist, valRange, indexRange, estimate;
    float fraction;
    while(start <= end && key >= array[start] && key <= array[end]) {
        dist = key - array[start];
        valRange = array[end] - array[start];
        fraction = dist / valRange;
        indexRange = end - start;
        estimate = start + (fraction * indexRange);
        if(array[estimate] == key) return estimate;
        if(array[estimate] < key) start = estimate + 1;
        else end = estimate - 1;
    }
    return -1;
}

int main() {
    int n, searchKey, loc;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử: " << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Nhập khóa tìm kiếm: ";
    cin >> searchKey;
    if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
        cout << "Mục tìm thấy tại vị trí: " << loc << endl;
    else
        cout << "Mục không tìm thấy trong danh sách." << endl;
}

Kết quả đầu ra

Nhập số lượng phần tử: 20
Nhập các phần tử: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Nhập khóa tìm kiếm: 780
Mục tìm thấy tại vị trí: 16