二分查找由于思想簡單，在經(jīng)典算法中最容易被初學(xué)者忽視猪狈。
看懂了書上的一種寫法后箱沦，就以為自己會了，而實(shí)際上是一看就會雇庙，一寫就廢谓形。
不信的話灶伊，先來看一個(gè)問題：
找出升序數(shù)組中小于等于目標(biāo)值的最大值？（數(shù)組中可能不包含目標(biāo)值）
如果感覺很棘手寒跳，別著急聘萨，看完本文你能隨手?jǐn)]出兩種不同的解法。如果你寫出來了童太，也別著急米辐，繼續(xù)看下去，你會發(fā)現(xiàn)你寫的不一定完美书释。好啦翘贮，不管怎樣，看完絕對不虧爆惧，哈哈狸页。
一、開門見山
不繞彎彎扯再，針對問題：找出升序數(shù)組中小于等于目標(biāo)值的最大值芍耘？
直接給出兩種二分查找的典型寫法，
第一種：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
return high; // 必須返回 high
}
第二種：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high + 1) >>> 1;
if(a[mid] > target) high = mid - 1;
else low = mid;
}
return low; // 返回 high 也可以
}
這兩種寫法最明顯的區(qū)別是熄阻，在 while 循環(huán)里斋竞，第一種是三分支判斷，第二種是兩分支判斷秃殉。
二分查找版坝初，找不同游戲：
- high 的初始值，有 a.length 和 a.length-1 兩種
- while 循環(huán)條件复濒，有 low < high 和 low <= high 兩種
- 取中位數(shù)，有 取左中位數(shù) 和 取右中位數(shù) 兩種
- 取中位數(shù)的寫法乒省，以取左中位數(shù)為例巧颈，有 low+(high-low)/2、low+((high-low)>>1)袖扛、(low+high)>>>1（推薦這種寫法）等砸泛。注意 low+high 可能溢出，最好不要寫成 (low+high)/2
- low 和 high 的更新蛆封，以 low 為例唇礁，有 low = mid 和 low = mid+1 兩種
- 判斷分支的個(gè)數(shù)，有兩分支和三分支兩種惨篱。
可見二分查找的寫法是多么靈活盏筐！
不過對于上面的找不同，有幾點(diǎn)需要說明一下砸讳。
high 的初值設(shè)置和 while 循環(huán)條件有關(guān)琢融，當(dāng)循環(huán)條件為 low <= high 時(shí)界牡，必須寫 a.length-1，否則兩種寫法都可以漾抬。
另外宿亡，只有兩分支寫法需要取右中位數(shù)和邊界更新為中位數(shù)（e.g. low = mid），后面會說到纳令。
簡單解釋一下挽荠，為什么 (low+high)>>>1 不用擔(dān)心溢出，溢出之所以出錯平绩，是因?yàn)橛幸徊糠謹(jǐn)?shù)值進(jìn)到了符號位圈匆，我們只要把符號位當(dāng)成是數(shù)值位，結(jié)果就是正確的馒过，而無符號右移臭脓，剛好就不會處理符號的問題。
二腹忽、第一種寫法：三分支二分查找（推薦寫法）
這種寫法来累，除了返回值以外基本上都可以閉著眼睛寫
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
由于 while 循環(huán)條件是 low <= high，所以退出循環(huán)時(shí)窘奏，low != high嘹锁，至于最終是返回 low 還是 high。記住下面這種圖就 OK 了着裹。
這幅圖的含義是领猾，如果二分查找的目標(biāo)值 target 不在數(shù)組中，那么最后退出循環(huán)時(shí)骇扇，high 指向數(shù)組中剛好小于 target 的值摔竿，low 指向數(shù)組中剛好大于 target 的值。
三少孝、第二種寫法：兩分支二分查找
while 循環(huán)條件是 low < high继低，退出循環(huán)時(shí)，一定有 low == high稍走，不用糾結(jié)返回 low 還是返回 high袁翁。
循環(huán)里只寫兩個(gè)分支，一個(gè)分支排除中位數(shù)婿脸，另一個(gè)分支不排除中位數(shù)粱胜，不再單獨(dú)對中位數(shù)做判斷。
根據(jù)“排除中位數(shù)的邏輯”狐树，會有以下兩種情況：
if(排除中位數(shù)的邏輯) low = mid + 1;
else high = mid;
if(排除中位數(shù)的邏輯) high = mid - 1;
else low = mid;
因?yàn)橛幸粋€(gè)邊界更新為中位數(shù)焙压，為了避免死循環(huán)，所以有 取左中位數(shù) 和 取右中位數(shù) 的區(qū)別。
例如下面的代碼就有陷入死循環(huán)的風(fēng)險(xiǎn)：
mid = (low + high) >>> 1; // 選擇左中位數(shù)
if(排除中位數(shù)的邏輯) high = mid - 1;
else low = mid;
當(dāng)候選區(qū)間只剩兩個(gè)元素時(shí)冗恨，此時(shí)求得的左中位數(shù)就是左邊界答憔，一旦進(jìn)入左邊界更新為中位數(shù)的邏輯分支，下一次循環(huán)掀抹，左邊界沒有變虐拓，求得的左中位數(shù)還是左邊界，左邊界還是不變傲武，就會陷入死循環(huán)蓉驹。
解決辦法是星澳，對于左邊界更新為中位數(shù)的情況感混，我們?nèi)∮抑形粩?shù)。對于右邊界更新為中位數(shù)的情況区转，我們?nèi)∽笾形粩?shù)疟位。
四瞻润、具體問題
4.1 找出升序數(shù)組中小于等于目標(biāo)值的最大值
前面已經(jīng)給出代碼，不再重復(fù)列出甜刻。
4.2 找出升序數(shù)組中大于等于目標(biāo)值的最小值
第一種寫法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
return low;
}
第二種寫法（小于目標(biāo)值的肯定不要绍撞，作為排除中位數(shù)的邏輯）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
4.3 找出升序數(shù)組中小于目標(biāo)值的最大值
第一種寫法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid - 1;
}
return high;
}
第二種寫法（大于等于目標(biāo)值的肯定不要，作為排除中位數(shù)的邏輯）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high + 1) >>> 1;
if(a[mid] >= target) high = mid - 1;
else low = mid;
}
return low;
}
4.4 找出升序數(shù)組中大于目標(biāo)值的最小值
第一種寫法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid + 1;
}
return low;
}
第二種寫法（小于等于目標(biāo)值的肯定不要得院，作為排除中位數(shù)的邏輯）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high) >>> 1;
if(a[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
五傻铣、最后
不是說第一種寫法 while 循環(huán)條件一定要是 low <= high，只是 low <= high 更好祥绞。不是說第二種寫法 while 循環(huán)條件一定要是 low < high非洲，只是寫 low < high 更好。
我還是推薦大家使用第一種寫法蜕径，代碼對稱两踏，寫法固定，好記兜喻，只需要記住那張圖就可以了梦染。當(dāng)然，第二種寫法也不是白看的虹统，當(dāng)你看到別人用第二種寫法時(shí)弓坞，能很快反應(yīng)過來隧甚，他寫的是什么车荔，寫的正不正確。
參考：leetcode 題解
