資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式來實現插值搜尋演算法
對於二分搜尋技術，將列表分成相等的部分。對於插值搜尋技術，該過程將嘗試使用插值公式找到確切的位置。找到估計位置後，它可以使用該位置分割列表。因為它每次都嘗試找到確切的位置，所以搜尋時間減少了。如果專案是均勻分佈的，則此技術可以輕鬆地找到專案。
插值搜尋技術的複雜性
時間複雜度：對於平均情況為 O(log2(log2 n))，對於最壞情況為 O(n)（當專案呈指數分佈時）
空間複雜度：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
演算法
interpolationSearch(array, start, end, key)
輸入：一個已排序的陣列、開始和結束位置以及搜尋鍵
輸出：金鑰的位置（如果找到），否則位置錯誤。
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示例程式碼
#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;
}輸出
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
更新於： 30-Jul-2019
985 次觀看
廣告