算法来源
对于插值查找，就是对于二分查找的优化，将二分查找中的mid = (low + high) / 2改为mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])。插值查找是根据查找关键子key与查找表中最大最小记录关键字比较后的查找方法，核心在于插值计算公式(key-a[low])/(a[high] - a[low])。
算法分析
时间复杂度依旧为O(logn)。
对于表长较大，而关键字分部比较均匀的查找表来说，平均性能要比折半好很多。
如果数组中的分部类似{1，100，200，1000，10000...10000}这种极端不均匀的数据，用插值法也不太合适。
javaScript:
function search(arr, key, left, right){
while(left < right){
if(arr[left] == key){
return left
}
if(arr[right] == key){
return right
}
let middle = left + (right-left)*((key-arr[left])/(arr[right]-arr[left]))
middle = Math.floor(middle)
if(arr[middle] == key){
return middle
}
if(key < arr[middle]){
return search(arr, key, left, middle-1)
} else {
return search(arr, key, middle+1, right)
}
}
return -1
}
let arr1 = [0, 9, 11, 39, 68, 88, 101]
console.log(search(arr1, 88, 0, arr1.length-1))
网友评论