插值查找算法
- 引言
- 什麼是內插補點查找算法
-
- 優化内容
- 內插補點查找思路
- 公式分析
- 內插補點查找算法的局限
- 代碼實作
引言
說是插值查找算法，我覺得叫不如叫內插補點查找算法更加貼切。因為是根據相關資料的內插補點來确定查找範圍的。本文的後續内容我就以內插補點查找算法，代替插值查找算法了。
什麼是內插補點查找算法
問到內插補點查找算法，那麼你就應該已經知道了什麼是二分查找算法了。
（什麼？你還不知道？點這裡了解二分查找算法）
簡單一點來說，內插補點查找算法是對二分查找算法的做了一些小小的優化。
優化内容
取中點值的公式不同。
在二分查找算法裡我們取mid的公式如下
為了後續的推導我們變換一下
但是在內插補點查找算法裡我們取mid的公式如下：
這就是兩種算法的差別所在。是以了解插值排序，隻需要看懂這個公式即可，接下來我們來分析這個公式吧。
內插補點查找思路
在講解這個公式之前，我們需要先知道內插補點查找的思路是什麼。
二分查找的思路是：直接分一半，然後每次處理一半。但是假如我們找的值在最左邊，或者最右邊，那麼就必須一次一次分割到最後才行了。
那麼有沒有可能我可以把查找範圍縮到更小，縮小到上次數組的1/3、1/4或者更小？這就是內插補點查找算法要做的事情，把查找的範圍縮的得更小。
公式分析
那麼是怎樣實作的呢？我們觀察兩個取mid的公式
差別就在于第一個參數，二分查找取值是1/2
而內插補點查找是
那麼我們來看這些變量的含義：
target : 查找的目标值
arr[left ] : 需要查找數組的左邊元素的值
arr[right] : 需要查找數組的右邊元素的值
是以當以上這個式子的值小于1/2時，那麼所取得的mid也更小，中點就越靠近左端的left。
那麼如果目标值在正好在mid左側那我們是不是就縮小了下一次查找的範圍？
請注意上面這段話
我們注意這樣的一種情況：當數組呈均勻分布時（比如0，2，4，6，8，16…這種），內插補點查找算法的算法需要幾次找到呢？我們看以下式子推導
假設最左側的值為 L
數組共有n個元素
相鄰兩數的內插補點為k
所求target 的下标為i
那麼target = L + i*k,
arr[ right ] - arr[ left ] = (n - 1) * k ,
right - left = n - 1。
代入上述式子就變成了
約分變換之後，你就得到
因為二分查找的起始位置是從0開始的 ，是以第一次查找的時候 得到 mid = i就是直接找到需要尋找的值的下标。
是以當數組呈均勻分布時，內插補點查找隻需要找一次即可找到所需要的結果。
內插補點查找算法的局限
看了上述的推導，是不是覺得內插補點排序很厲害。但是還記得我讓你注意的那句話嗎？
雖然我們可以縮小某一側的範圍，但是我們并不能保證所尋找資料就在那一側。也就是說，我按mid把數組分為：左側占原數組1/3 , 右側占2/3，但是我所需要找到的資料在右側。那麼此時我需要查找的範圍時2/3 比 二分查找的1/2更大，所需要查找的資料更多。
比如這樣的一個數組[0 , 1, 5 , 7, 8 , 12, 100]，我們的 target = 8。按照上述公式
得到的mid為 0.48 向下取整為0，下一次查找的範圍為[ 1 , 6]
比二分查找的得到的範圍[ 4 ， 6]更大。
在上面的情況下，內插補點查找算法隻能從頭到尾依次查找了，退化成順序查找算法。
是以內插補點排序并很不是穩定的。但如果能确定數組呈均勻分布或者相鄰值的內插補點并不很大，則內插補點查找算法優于二分查找算法。
代碼實作
public class Test {
/*
* 插值查找
*/
public static int interpolationSearch(int[] arr, int target , int left , int right) {
if(target < arr[left] || target > arr[right] || left > right){
return -1;
}
int leftToTarget = target - arr[left];
int rightToLeft = arr[right] - arr[left];
int num = right - left;
//中間的值的下标 注意此行與二分查找的差別
int mid = left + leftToTarget*num/rightToLeft;
System.out.println("找了一次，中間值為：" + mid);
//目标值小于中間值 取左側
if(arr[mid] > target && left <= right) {
//遞歸左側
return interpolationSearch(arr,target , left , mid-1);
}else if(arr[mid] < target && left <= right) {
//目标值大于中間值 取右側 并且遞歸
return interpolationSearch(arr,target, mid+1 , right);
}else {
//不大于也不小于 則是相等
return mid;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("======== 內插補點查找分布略微不均勻數組 ===========");
int arr[] = {1 ,4, 9, 15, 27, 49, 128, 157};
int result = interpolationSearch(arr, 9, 0, arr.length - 1);
System.out.println(result==-1?"未找到元素！":"查找成功！" + 9 + "對應下标： " + result);
System.out.println("======== 內插補點查找分布均勻數組 ===========");
int arr1[] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ,20};
int target = 8;
int result1 = interpolationSearch(arr1, target, 0, arr1.length - 1);
System.out.println(result1==-1?"未找到元素！":"查找成功！" + target + "對應下标： " + result1);
System.out.println("======== 內插補點查找分布極其不均勻數組 ===========");
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,99999};
int target2 = 8;
int result2 = interpolationSearch(arr2, target2, 0, arr2.length - 1);
System.out.println(result2==-1?"未找到元素！":"查找成功！" + target2 + "對應下标： " + result2);
}
}
測試結果如下