一庄撮、介紹
1凹嘲、插值查找算法類似于二分查找堂飞，不同的是插值查找每次從自適應(yīng) mid 處開始查找昼接。
2爽篷、將折半查找中的求mid索引的公式,low表示左邊索引left,high表示右邊索引right. key 就是前面我們講的 findVal
在這里插入圖片描述
3、int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/
對應(yīng)前面的代碼公式:
int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
4慢睡、舉例說明插值查找算法 1-100 的數(shù)組
在這里插入圖片描述
二逐工、代碼
public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = {1, 8, 10, 89, 1000, 1000, 1234};
int index = search(arr, 0, arr.length - 1, 89);
System.out.println("index = " + index);
}
private static int search(int[] array, int left, int right, int key) {
while (left <= right) {
if (array[right] == array[left]) {
if (array[right] == key)
return right;
else return -1;
}
int middle = left + ((key - array[left]) / (array[right] - array[left])) * (right - left);
if (array[middle] == key) {
return middle;
}
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
三、插值查找注意事項:
- 對于數(shù)據(jù)量較大漂辐，關(guān)鍵字分布比較均勻的查找表來說泪喊，采用插值查找, 速度較快.
- 關(guān)鍵字分布不均勻的情況下，該方法不一定比折半查找要好
