今天想來說說二分查找，因為最近筆者的同學(xué)在面試時正好遇到了，而自己以前還真沒認(rèn)真研究過。
說起二分查找，對算法和數(shù)據(jù)結(jié)構(gòu)比較熟悉的都知道這是一個復(fù)雜度為 O(logN) 的典型分治算法，它的用途是在有序數(shù)組中查找某個數(shù)是否存在。但就是這么聽起來很普通的算法卻常常很難完全寫對。
- 據(jù)D.Knuth在《計算機程序設(shè)計的藝術(shù) 第3卷：排序和查找》書中指出，雖然二分查找1946年就公諸于世，但1962年才有人寫出沒有 bug 的二分查找程序。
- 除此之外，就連我們熟悉的 Java 語言里 JDK 的二分查找
java.util.Arrays.binarySearch中也曾有一個隱藏了10年之久bug!（文末附bug鏈接）不過，這個bug已經(jīng)不是什么新鮮事了，是 JDK5 時代的產(chǎn)物了，不過我們可以再來回顧一下，看看我們平常是不是就在寫bug，是不是真應(yīng)了那個表情包“喲，寫bug呢”??
// 這段代碼有毒，請勿模仿
public static int binarySearch(int[] a, int key){
int low = 0;
int high = a.length - 1;
while(low <= high){
int mid = (low + high) >> 1;
int midVal = a[mid];
if(midVal < key)
low = mid + 1;
else if(midVal > key)
high = mid -1;
else
return mid;
}
return - (low + 1);
}
乍一看這段代碼似乎也沒什么問題，但其中的幾處細(xì)節(jié)是需要注意的，而這幾處細(xì)節(jié)恰巧也是面試中經(jīng)常遇見的（筆者的同學(xué)最近面試某大廠就被問到了）。
實際上，上述代碼的問題就出在int mid = (low + high) >> 1，這句可能導(dǎo)致整數(shù)溢出，此時該方法就會拋出數(shù)組越界的異常，這個bug直接導(dǎo)致了 JDK6 之前的 binarySearch 無法正確處理大數(shù)組的情況。這個bug直到 JDK6 才得到修復(fù)。修復(fù)后代碼是int mid = (low + high) >>> 1，將帶符號右移修復(fù)成無符號右移，目前 JDK8里面的 binarySearch 就是這樣。當(dāng)然，除了這種方法之外，我們還可以這樣寫int mid = low + ((high - low) >> 1)?；叵胍幌?，你是不是也曾寫過類似bug呢？
當(dāng)然，今天學(xué)習(xí)時除了看到這個比較明顯的細(xì)節(jié)外，還看到有兩個地方也需要注意：
- 判斷循環(huán)體是否終止的語句的編寫
- 邊界值 low, high 和區(qū)間值這三個地方要保持一致
對于第2點，具體一點就是，如果令 high = n - 1 (n是數(shù)組長度)，則 while 的循環(huán)條件為 low <= high，從而更新右邊界位置的時候為 high = mid - 1；而如果令 high = n，則 while 循環(huán)的循環(huán)條件為 left < right，從而更新右邊界位置的時候為 high = mid。同時，mid 的計算不能寫在循環(huán)外，否則無法得到更新。
下面是一份無遞歸版本的參考代碼：
public static int binarySearch(int[] a, int n, int key){
int left = 0;
int right = n - 1;
while (left <= right){
int mid = left + ((right - left) >> 1);
if (a[mid] > key)
right = mid - 1;
else if(a[mid] < key)
left = mid + 1;
else
return mid;
}
return -1;
}
當(dāng)然，上述代碼并沒有判斷輸入異常之類的，還有遞歸版本等等，大家可以看看文末提供的二分搜索算法維基百科上面的例子。
總結(jié)一下，二分查找大的方面需要注意三點：
- mid 賦值問題，注意溢出情況。
- 判斷 while 循環(huán)體是否終止的語句的編寫
- 邊界值 left, right 和區(qū)間值這三個地方要保持一致
參考：
