203，查找-插值查找

二分法查然效率很高，但我們為什麼要和中間的值進行比較，如果我們和數組1/4或者3/4部分的值進行比較可不可以呢，對于一個要查找的數我們不知道他大概在數組的什麼位置的時候我們可以使用二分法進行查找。但如果我們知道要查找的值大概在數組的最前面或最後面的時候使用二分法查找顯然是不明智的。比如我們查字典的時候如果是a或者b開頭的我們一般會在前面找，如果是y或者z開頭的我們一般偏向于往後面找，這個時候如果我們使用二分法從中間開始找顯然是不合适的。之前二分法查找的時候我們比較的是中間值，mid=low+1/2*(high-low);但插值查找的時候我們比較的不是中間值，是mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，我們來看下插值查找的代碼。

他和二分法查找代碼很相似，隻不過計算middle的方式不一樣。再來看一下遞歸的版本