查找-插值查找

1.插值查找前言

現在我們的新問題是，為什麼一定要折半，而不是折四分之一或者折更多呢？

例如，在英文詞典裡查”apple”,你下意識裡翻開詞典是翻前面的書頁還是後面的書頁呢？如果再讓你查”zoo”，你又怎麼查？很顯然，這裡你絕對不會是從中間開始查起，而是有一定目的的往前或往後翻。

2.插值查找算法

基于折半查找代碼，我們略微變換等式後得到：

mid=low+high2=low+12(high−low) 也就是mid等于最低下标low加上最高下标high與low的差的一半。算法科學家們考慮的就是将這個1/2進行改進，改進為下面的計算方案：

low+k−a[low]a[high]−a[low](high−low)

将1/2改成了 key−a[low]a[high]−a[low] 有什麼道理呢？假設a[11]={0,1,16,24,35,47,59,62,73,88,99}，low=1，high=10，則a[low]=1，a[high]=99，如果我們要找的是key=16時，按原來的折半查找的做法，我們需要四次才可以得到結果，但如果使用新辦法， key−a[low]a[high]−a[low] =（16-1）/（99-1）≈0.153，即mid≈1+0.153*(10-1)=2.377取整得到mid=2，我們隻需要兩次查找到結果了，顯著大大提高了查找的效率。

換句話說，我們隻需要在折半查找算法的代碼中更改一下一行代碼如下：

mid=low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值

就得到了另一種有序表查找算法，插值查找法

3.插值查找定義

插值查找(Interpolation Search)是根據要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找方法，其核心就在于查找的關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找方法，其核心就在于插值的計算公式 key−a[low]a[high]−a[low] 。

4.插值查找複雜度

從時間複雜度來看，它也是O(logn)，但對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好得多。反之，數組中如果分布類似{0,1,2,2000,2001,……,999998,999999}這種極端不均勻的資料，用插值查找未必是很合适的選擇。