二分查找算法及其變種

前言

二分查找算法也稱為折半查找算法，是一種在查找算法中普遍使用的算法。其算法的基本思想是：在有序表中，取中間的記錄作為比較關鍵字，若給定值與中間記錄的關鍵字相等，則查找成功；若給定的值小于中間記錄的關鍵字，則在中間記錄的左半區間繼續查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區間繼續查找；不斷重複這個過程，直到查找成功。否則查找失敗。這個思想與孔子中的中庸思想和相似。

二分查找算法的實作

基于上述的思想，可以很快寫出如下代碼：

實際上，二分查找的過程可以繪制成一棵二叉樹，每次二分查找的過程就相當于把原來的樹劃分為兩棵子樹，是以每次二分之後下次就隻需要查找其中一半的資料就可以了。那麼二分查找算法的時間複雜度是多少呢？在最好的情況下，隻需要查找一次就可以了，因為這時候中間記錄的關鍵字與要查找的key是相等，自然一次就夠了。在最壞的情況下是從根節點查找到最下面的葉子結點，這個過程需要的時間複雜度是o(logn)。

需要注意的是，雖然二分查找算法的效率很高（這也是二分查找算法被廣泛應用的原因），但是仍然是有使用條件的：有序。就是說在需要頻繁進行插入或者删除操作的資料記錄中使用二分查找算法不太劃算，因為要維持資料的有序還需要額外的排序開銷。

二分查找算法的變種一：插值查找算法

可以發現二分查找每次都是選取中間的那個記錄關鍵字作為劃分依據的，那為什麼不可以是其他位置的關鍵字呢？在有些情況下，使用二分查找算法并不是最合适的。舉個例子：在1-1000中，一共有1000個關鍵字，如果要查找關鍵字10，按照二分查找算法，需要從500開始劃分，這樣的話效率就比較低了，是以有人提出了插值查找算法。說白了就是改變劃分的比例，比如三分或者四分。

插值查找算法對二分查找算法的改進主要展現在mid的計算上，其計算公式如下：

mid=low+key−a[low]a[high]−key(high−low)

而原來的二分查找公式是這樣的：

mid=low+12(high−low)

是以我們發現主要變化的地方是12這個系數。其思想可以總結如下：插值查找是根據要查找的關鍵字的key與查找表中最大最小記錄的關鍵字比較之後的查找算法，其核心是上述計算mid的計算公式。由于大體架構與二分查找算法是一緻的，是以時間複雜度仍然是o(logn)。

二分查找算法變種二：斐波那契查找算法

從前面的分析中可以看到，無論劃分的關鍵字太大或者太小都不合适，是以又有人提出了斐波那契查找算法，其利用了黃金分割比原理來實作的。

一個數列如果滿足f(n)=f(n-1)+f(n-2)，則稱這個數列為斐波那契數列。在斐波那契查找算法中計算mid的公式如下：

mid=low+f(k−1)−1

其實作代碼如下：

可以看出斐波那契查找算法的核心是如果要查找的記錄在右側，則左邊就不會再去查找了，不斷反複進行下去，知道查找成功。雖然斐波那契查找算法的時間複雜度也是o(logn)，但是從性能看，仍然是優于二分查找算法的。