前言

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

二分查找算法的實現(xiàn)

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

public int binarySearch(int[] a,int key) {int low = 0;int high = a.length - 1;int mid = 0;while(low <= high){mid = (low + high) / 2;if(a[mid] == key) return mid;if(a[mid] > key) high = mid - 1;if(a[mid] < key) low = mid + 1;}return -1;}

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

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

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

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

插值查找算法對二分查找算法的改進主要體現(xiàn)在mid的計算上，其計算公式如下：

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

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

mid=low+12(high?low)

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

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

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

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

mid=low+F(k?1)?1

其實現(xiàn)代碼如下：

package com.rhwayfun.algorithm.search;public class FibonacciSearch {public int fibonacciSearch(int[] a,int key){int low = 0,high = a.length - 1,mid = 0,k = 0,i =0;//計算數(shù)組的長度的值在斐波那契數(shù)列的位置while(a.length > F(k) - 1){k++;}//將不滿的數(shù)值補全int[] newArray = new int[F(k) - 1];System.arraycopy(a, 0, newArray, 0, a.length);for(i = a.length; i < F(k) - 1; i++)newArray[i] = a[a.length - 1];a = newArray;//查找過程while(low <= high){mid = low + F(k-1) - 1;if(key < a[mid]){high = mid - 1;k = k - 1;}else if(key > a[mid]){low = mid + 1;k = k - 2;}else{if(mid < a.length){return mid;}else{//說明是補全之后的數(shù)值return a.length - 1;}}}return 0;}//返回第n項斐波那契數(shù)列的值private int F(int n) {if(n == 0){return 0;}else if(n == 1){return 1;}int one = 1;int two = 0;int sum = 0;for (int i = 2; i <= n; i++) {sum = one + two;two = one;one = sum;}return sum;}public static void main(String[] args) {int[] a = {0,1,16,24,35,47,59,62,73,88,99};int i = new FibonacciSearch().fibonacciSearch(a, 59);System.out.println(a[i]);} }

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

總結

以上是生活随笔為你收集整理的二分查找算法及其变种的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。