Đố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, quy trình sẽ cố gắng xác định vị trí chính xác bằng công thức nội suy. Sau khi tìm thấy vị trí ước tính, nó có thể tách danh sách bằng cách sử dụng vị trí đó. Vì nó cố gắng tìm vị trí chính xác mọi lúc, vì vậy thời gian tìm kiếm giảm xuống. Kỹ thuật này có thể dễ dàng tìm thấy các mục nếu các mục được phân phối đồng đều.
Sự phức tạp của Kỹ thuật Tìm kiếm Nội suy
- Độ phức tạp về thời gian: O (log2 (log2 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 được phân phối theo cấp số nhân)
- 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: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 The search key 780 Output: Item found at location: 16
Thuật toán
interpolationSearch(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 while start <= end AND key >= array[start] AND key <= array[end] do dist := key – array[start] valRange := array[end] – array[start] fraction := dist / valRange indexRange := end – start estimate := start + (fraction * indexRange) if array[estimate] = key then return estimate position if array[estimate] < key then start := estimate + 1 else end = estimate -1 done return invalid position End
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]; //range of value
fraction = dist / valRange;
indexRange = end - start;
estimate = start + (fraction * indexRange); //estimated position of the key
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 << "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 = interpolationSearch(arr, 0, n-1, 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: 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 to search in the list: 780 Item found at location: 16