二分查找之进阶（插值查找）

Interpolation Search

1. 二分查找即是折半查找，即把数据分成2份进行比较判断。（前提是有序列表）

二分查找代码 function bsearch (list,item) { //有序队列的二分查找 let lindex = 0 let hindex = list.length-1 let mid while (lindex<=hindex) { mid = Math.floor((lindex+hindex)/2) let guess = list[mid] if(guess==item){ return mid }else if(guess>item){ hindex = mid - 1 }else{ lindex = mid + 1 } } return null }

2. 如果要查找的数十分接近于low端或者height端，那么用四分查找会比二分查找更快（如何找到类似于二分或者四分的这个值？）

插值查找代码 function interpolationSearch (list,searchItem) { let low = 0 let height = list.length-1 let mid while (low<=height) { mid = Math.floor(low+(height-low)*((searchItem-list[low])/(list[height]-list[low]))) let guess = list[mid] if(guess==searchItem){ return mid }else if(guess>searchItem){ height = mid - 1 }else{ low = mid + 1 } } return null }

3. 插值查找与二分查找关键不同在于找mid值所用的公式

二分查找：mid=low+(height-low)/2=(low+height)/2 插值查找：mid=low+(height-low)*((item-list[low])/(list[height]-list[low])) 从而可知，当(item-list[low])/(list[height]-list[low])=1/2时就为二分查找

插值查找适用范围

1.插值查找的前提同样是有序列表 2.而且列表中的值是均匀分布的，如果列表是 [1,2,3,1000,10000,100000] 这样值不均匀分布的情况，则不适合 （插值查找的本质就是用查找值来推断mid下标索引的位置）