Đố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ách sử dụ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.
Mức độ 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 (log 2 (log 2 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ặt hàng được phân phối theo cấp số nhân)
-
Độ phức tạp của không gian:O (1)
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
nội suy Tìm kiếm (mảng, bắt đầu, kết thúc, khóa)
Đầu vào :Một mảng được 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 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 Mã mẫu
#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