二分查找究竟有多重要？《編程之美》第2.16節(jié)的最長(zhǎng)遞增子序列算法，如果想實(shí)現(xiàn)O(n2)到O(nlogn)的時(shí)間復(fù)雜度下降，必須借助于二分算法的變形。其實(shí)很多算法都是這樣，如果出現(xiàn)了在有序序列中元素的查找，使用二分查找總能提升原先使用線性查找的算法。
然而，雖然很多人覺得二分查找簡(jiǎn)單，但隨手寫一寫卻不能得到正確的結(jié)果：死循環(huán)、邊界條件等等問題伴隨著出現(xiàn)�！毒幊讨榄^》第四章提到：提供充足的時(shí)間，僅有約10%的專業(yè)程序員能夠完成一個(gè)正確的二分查找。當(dāng)然，正確的二分查找和變體在算法書籍以及網(wǎng)絡(luò)上隨處可得，但是如果不加以理解，如何掌握？理解時(shí)，又往往因想不清楚，一知半解，效果有限。我在看相關(guān)的變體算法時(shí)就覺得一片茫然，不得要領(lǐng)：或許這個(gè)算法可以這么寫，稍微變下要求就不能這么寫了；舉正例說明算法在某些情況下可以正常工作、舉反例說明算法有錯(cuò)固然可行，但僅有例子是不夠的，怎樣一勞永逸地證明自己幾經(jīng)修改的算法之正確？如果每一個(gè)變體都進(jìn)行孤立地理解，那么太花費(fèi)時(shí)間，而且效果也不好。如何解決這個(gè)問題？在思考方法和查閱書籍之后發(fā)現(xiàn)，還是要靠循環(huán)不變式來(lái)完成算法正確性的理論支撐。
或許你曾了解過循環(huán)不變式，但如果不使用的話，是看不到它的強(qiáng)大之處的：不僅僅能幫助你證明算法正確性，同時(shí)也幫助你理解算法，甚至能幫助你在基本算法的基礎(chǔ)上，構(gòu)造出符合要求的相應(yīng)算法變體。這些都將在后文的各個(gè)算法說明中看到。
知識(shí)準(zhǔn)備
結(jié)合《算法導(dǎo)論》和《編程珠璣》，下面說明循環(huán)不變式的概念與性質(zhì)。
循環(huán)不變式主要用來(lái)幫助理解算法的正確性。形式上很類似與數(shù)學(xué)歸納法，它是一個(gè)需要保證正確斷言。對(duì)于循環(huán)不變式，必須證明它的三個(gè)性質(zhì)：
初始化：它在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的。
保持：如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應(yīng)該保持正確。
終止：循環(huán)能夠終止，并且可以得到期望的結(jié)果。
文章說明
(1)在推導(dǎo)每次數(shù)組減少的長(zhǎng)度時(shí)，mid是不能代換成(left+right)/2的。這種形式代表了非整型的運(yùn)算，沒有舍去小數(shù)部分，而在代碼中實(shí)際的mid是會(huì)舍去小數(shù)部分的。
(2)代碼部分的=和==意義同C語(yǔ)言；文字說明部分的=代表賦值，==代表等式推導(dǎo)或者邏輯判斷，由上下文而定。
(3)除了3和5外，最初的各個(gè)變體代碼參考于：二分查找，你真的會(huì)嗎？ 為了符合思路的前后連貫和說明循環(huán)不變式，做了一些修改。原文的測(cè)試很方便，讀者可以自行參考。
1.二分查找值為key的下標(biāo)，如果不存在返回-1。
循環(huán)不變式：
如果key存在于原始數(shù)組[0,n-1]，那么它一定在[left,right]中。
初始化：
第一輪循環(huán)開始之前，處理的數(shù)組就是原始數(shù)組，這時(shí)顯然成立。
保持：
每次循環(huán)開始前，key存在于待處理數(shù)組array[left, ..., right]中。
對(duì)于array[mid]<key，array[left, ..., mid]均小于key，key只可能存在于array[mid+1, ..., right]中；
對(duì)于array[mid]>key，array[mid, ..., right]均大于key，key只可能存在于array[left, ..., mid-1]中；
對(duì)于array[mid]==key，查找到了key對(duì)應(yīng)的下標(biāo)，直接返回。
在前兩種情況中，數(shù)組長(zhǎng)度每次至少減少1（實(shí)際減少的長(zhǎng)度分別是mid-left+1和right-mid+1），直到由1（left==right）變?yōu)?（left>right），不會(huì)發(fā)生死循環(huán)。
終止：
結(jié)束時(shí)，left>right，待處理數(shù)組為空，表示key不存在于所有步驟的待處理數(shù)組，再結(jié)合每一步排除的部分?jǐn)?shù)組中也不可能有key，因此key不存在于原數(shù)組。
int binsearch(int * array, int length, int key)
{
if(!array)
return -1;
int left = 0, right = length,mid;
while(left <= right)
{
mid = (left + right)/2;
if(array[mid] < key)
{
left = mid + 1;
}else if(array[mid] > key)
{
right = mid - 1;
}else
return mid;
}
return -1;
}2.二分查找返回key(可能有重復(fù))第一次出現(xiàn)的下標(biāo)x，如果不存在返回-1
循環(huán)不變式：
如果key存在于數(shù)組，那么key第一次出現(xiàn)的下標(biāo)x一定在[left,right]中，且有array[left]<=key, array[right]>=key。
初始化：
第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時(shí)顯然成立。
保持：
每次循環(huán)開始前，如果key存在于原數(shù)組，那么x存在于待處理數(shù)組array[left, ..., right]中。
對(duì)于array[mid]<key，array[left, ..., mid]均小于key，x只可能存在于array[mid+1, ..., right]中。數(shù)組減少的長(zhǎng)度為mid-left+1，至少為1。
否則，array[mid]>=key, array[mid]是array[mid, ..., right]中第一個(gè)大于等于key的元素，后續(xù)的等于key的元素（如果有）不可能對(duì)應(yīng)于下標(biāo)x，舍去。此時(shí)x在[left, ..., mid]之中。數(shù)組減少的長(zhǎng)度為right-(mid+1)+1，即right-mid，根據(jù)while的條件，當(dāng)right==mid時(shí)為0。此時(shí)right==left，循環(huán)結(jié)束。
終止：
此時(shí)left>=right。在每次循環(huán)結(jié)束時(shí)，left總是x的第一個(gè)可能下標(biāo)，array[right]總是第一個(gè)等于key或者大于key的元素。
那么對(duì)應(yīng)于left==right的情況，檢查array[left]即可獲得key是否存在，若存在則下標(biāo)為x；
對(duì)于left>right的情況，其實(shí)是不用考慮的。因?yàn)閘eft==上一次循環(huán)的mid+1，而mid<=right。若mid+1>right，意味著mid == right，但此時(shí)必有l(wèi)eft == right，這一輪循環(huán)從開始就不可能進(jìn)入。
int binsearch_first(int * array, int length,int key)
{
if(!array)
return -1;
int left = 0, right = length-1,mid;
while(left < right)
{
mid = (left + right)/2;
if(array[mid] < key)
left = mid+1;
else
right = mid;
}
if(array[left] == key)
return left;
return -1;
}3.二分查找返回key(可能有重復(fù))最后一次出現(xiàn)的下標(biāo)x，如果不存在返回-1（模仿2的第一版）
循環(huán)不變式：
如果key存在于數(shù)組，那么key最后一次出現(xiàn)的下標(biāo)x一定在[left,right]中，且有array[left]<=key, array[right]>=key。
初始化：
第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時(shí)顯然成立。
保持：
每次循環(huán)開始前，如果key存在于原數(shù)組，那么x存在于待處理數(shù)組array[left, ..., right]中。
對(duì)于array[mid]<key，array[left, ..., mid]均小于key，x只可能存在于array[mid+1, ..., right]中。數(shù)組減少的長(zhǎng)度為mid-left+1，至少為1。
對(duì)于array[mid]==key, array[mid]是array[left, ..., mid]中最后一個(gè)值為key的元素，那么x的候選只能在array[mid, ... ,right]中，數(shù)組減少長(zhǎng)度為mid-left。除非left == right或left == right-1，否則數(shù)組長(zhǎng)度至少減小1。由于while的條件，只有后一種情況可能發(fā)生，如果不進(jìn)行干預(yù)會(huì)陷入死循環(huán)，加入判斷分支即可解決。
對(duì)于array[mid]>key, array[mid, ..., right]均大于key，x只可能在[left, ..., mid-1]之中。數(shù)組減少的長(zhǎng)度為(right-mid)+1，同樣至少為1。
終止：
此時(shí)left>=right,right總是從數(shù)組末尾向開始的倒序中第一個(gè)候選的x，檢查它的值是否符合要求即可。
而left總是上一輪刪掉失去x資格的元素后的第一個(gè)元素，不過這里用不到。
說明：
與上一種不同，這個(gè)算法不能簡(jiǎn)單地根據(jù)對(duì)稱，從上一個(gè)算法直接改過來(lái)，由于整數(shù)除法總是舍棄小數(shù)，mid有時(shí)會(huì)離left更近一些。所以這種算法只是沿著上一個(gè)算法思路的改進(jìn)，看上去并不是很漂亮。
int binsearch_last(int * array, int length, int key)
{
if(!array)
return -1;
int left = 0, right = length,mid;
while(left < right)
{
mid = (left + right)/2;
if(array[mid] > key)
right = mid - 1;
else if(array[mid] == key)
if(left == mid)
if(array[right] == key)
return right;
else
return left;
else
left = mid;
else
left = mid + 1;
}
if(array[right] == key)
return right;
return -1;
}4.二分查找返回key(可能有重復(fù))最后一次出現(xiàn)的下標(biāo)x，如果不存在返回-1（修改版）
根據(jù)3中的討論，可以發(fā)現(xiàn)不能直接照搬的原因是mid=(left+right)/2的舍棄小數(shù)，在left+1==right且array[left]=key時(shí)，如果不加以人為干預(yù)會(huì)導(dǎo)致死循環(huán)。既然最終需要干預(yù)，干脆把需要干預(yù)的時(shí)機(jī)設(shè)置為終止條件就行了。
使用while(left<right-1)可以保證每次循環(huán)時(shí)數(shù)組長(zhǎng)度都會(huì)至少減一，終止時(shí)數(shù)組長(zhǎng)度可能為2(left+1==right)、1(left==mid，上一次循環(huán)時(shí)right取mid==left)，但是不可能為0。(每一次循環(huán)前總有l(wèi)eft<=mid<=right，無(wú)論令left=mid還是令right=mid，都不會(huì)發(fā)生left>right)。同3一樣，right總是指向數(shù)組中候選的最后一個(gè)可能為key的下標(biāo)，此時(shí)只需先檢查right后檢查left是否為key就能確定x的位置。這樣就說明了循環(huán)不變式的保持和終止，就不再形式化地寫下來(lái)了。
對(duì)于兩種情況的合并：array[mid] == key時(shí)，mid有可能是x，不能將其排除；array[mid]<key時(shí)，如果讓left = mid+1，不會(huì)違反循環(huán)不變式的條件。但是由上面的討論可知，將left=mid也是可以的，在達(dá)到終止條件前能保證數(shù)組長(zhǎng)度單調(diào)減少。因此把兩種情況合并成最終形式。
int binsearch_last_v2(int * array, int length, int key)
{
if(!array) return -1;
int left =0, right = length-1,mid;
while(left < right -1)
{
mid = (left + right)/2;
if(array[mid] <= key)
left = mid;
else
right = mid;
}
if(array[right] == key)
return right;
else if(array[left] == key)
return left;
else
return -1;
}5.二分查找返回key(可能有重復(fù))最后一次出現(xiàn)的下標(biāo)x，如果不存在返回-1（利用2的方法）
如果想最大限度地利用已有的函數(shù)，那么把需要處理的數(shù)組倒序，然后直接使用方法2，再把得到的第一次出現(xiàn)的下標(biāo)做一次減法就可以得到最后一次出現(xiàn)的下標(biāo)，略。
6.二分查找返回剛好小于key的元素下標(biāo)x，如果不存在返回-1
如果第一反應(yīng)是通過2的方法找出第一個(gè)為key的元素，返回它的下標(biāo)減1，那么就錯(cuò)了：這個(gè)二分查找并沒有要求key本身在數(shù)組中。
循環(huán)不變式：
如果原始數(shù)組中存在比key小的元素，那么原始數(shù)組中符合要求的元素存在于待處理的數(shù)組。
初始化：
第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時(shí)顯然成立。
保持：
每次循環(huán)開始前，x存在于待處理數(shù)組array[left, ..., right]中。
先用一個(gè)循環(huán)的條件為right>=left，違反則意味著x不存在。寫下array[mid]的比較判斷分支：
(1) array[mid]<key, 意味著x只可能在array[mid, ..., right]之間，下一次循環(huán)令left = mid，數(shù)組長(zhǎng)度減少了(mid-1)-left+1 == mid-left，這個(gè)長(zhǎng)度減少量只有在right-left<=1時(shí)小于1。
(2)array[mid]>=key，意味著x只可能在array[left ,... ,mid-1]之間，下一次循環(huán)令right = mid-1，同樣推導(dǎo)出數(shù)組長(zhǎng)度至少減少了1。
這樣，把循環(huán)條件縮小為right>left+1，和4一樣，保證了(1)中每次循環(huán)必然使數(shù)組長(zhǎng)度減少，而且終止時(shí)也和4的情況類似：終止時(shí)待處理數(shù)組長(zhǎng)度只能為2或1或者空（left>right）。
終止：
接著保持中的討論，結(jié)束時(shí)，符合的x要么在最終的數(shù)組中，要么既不在最終的數(shù)組中也不在原始的數(shù)組中（因?yàn)槊恳淮窝h(huán)都是剔除不符合要求的下標(biāo)）。
數(shù)組長(zhǎng)度為2時(shí)，right==left+1，此時(shí)先檢查right后檢查left。如果都不符合其值小于key，那么返回-1。數(shù)組長(zhǎng)度為1時(shí)，只用檢查一次；數(shù)組長(zhǎng)度為0時(shí)，這兩個(gè)都是無(wú)效的，檢查時(shí)仍然不符合條件。把這三種情況綜合起來(lái)，可以寫出通用的檢查代碼。反過來(lái)，根據(jù)精簡(jiǎn)的代碼來(lái)理解這三種情況比正向地先給出直觀方法再精簡(jiǎn)要難一些。
int binsearch_last_less(int * array, int length, int key)
{
if(!array)
return -1;
int left = 0, right = length,mid;
while(left < right - 1)
{
mid = (left + right)/2;
if(array[mid] < key)
left = mid;
else
right = mid - 1;
}
if(array[right] < key)
return right;
else if(array[left] < key)
return left;
else
return -1;
}7.二分查找返回剛好大于key的元素下標(biāo)x，如果不存在返回-1
和6很類似，但如果只是修改循環(huán)中下標(biāo)的改變而不修改循環(huán)條件是不合適的，下面仍要進(jìn)行嚴(yán)謹(jǐn)?shù)恼f明和修正。
循環(huán)不變式：
如果原始數(shù)組中存在比key大的元素，那么原始數(shù)組中符合要求的元素對(duì)應(yīng)下標(biāo)x存在于待處理的數(shù)組。
初始化：
第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時(shí)顯然成立。
保持：
每次循環(huán)開始前，x存在于待處理數(shù)組array[left, ..., right]中。
仍然先把執(zhí)行while循環(huán)的條件暫時(shí)寫為right>=left，違反則意味著x不存在。寫下array[mid]的比較判斷分支：
(1) array[mid]<=key, 意味著x只可能在array[mid+1, ..., right]之間，下一次循環(huán)令left = mid，數(shù)組長(zhǎng)度減少了mid-left+1，減少量至少為1。
(2)array[mid]>key，意味著x只可能在array[left ,... ,mid]之間，下一次循環(huán)令right = mid，數(shù)組長(zhǎng)度減少了right-(mid+1)+1== right-mid，只有在right==mid時(shí)為0，此時(shí)left==right==mid。因此，循環(huán)條件必須由right>=left收縮為right>left才能避免left==right時(shí)前者會(huì)進(jìn)入的死循環(huán)。
終止：
由循環(huán)的終止條件，此時(shí)left>=right。類似2的分析，left>right是不可能的，只有l(wèi)eft==right。此時(shí)檢查array[right]>key成立否就可以下結(jié)論了，它是唯一的候選元素。
補(bǔ)充說明：
如果是對(duì)數(shù)組進(jìn)行動(dòng)態(tài)維護(hù)，返回值-1可以改為length+1，表示下一個(gè)需要填入元素的位置。
int binsearch_first_more(int * array, int length, int key)
{
if(!array)
return -1;
int left = 0, right = length-1,mid;
while(left < right)
{
int mid = (left+right)/2;
if(array[mid] <= key)
left = mid + 1;
else
right = mid;
}
if(array[right] > key)
return right;
return -1;
}8.總結(jié)：如何寫出正確的二分查找代碼？
結(jié)合以上各個(gè)算法，可以找出根據(jù)需要寫二分查找的規(guī)律和具體步驟，比死記硬背要強(qiáng)不少，萬(wàn)變不離其宗嘛：
(1)大體框架必然是二分，那么循環(huán)的key與array[mid]的比較必不可少，這是基本框架;
(2)循環(huán)的條件可以先寫一個(gè)粗略的，比如原始的while(left<=right)就行，這個(gè)循環(huán)條件在后面可能需要修改；
(3)確定每次二分的過程，要保證所求的元素必然不在被排除的元素中，換句話說，所求的元素要么在保留的其余元素中，要么可能從一開始就不存在于原始的元素中；
(4)檢查每次排除是否會(huì)導(dǎo)致保留的候選元素個(gè)數(shù)的減少？如果沒有，分析這個(gè)邊界條件，如果它能導(dǎo)致循環(huán)的結(jié)束，那么沒有問題；否則，就會(huì)陷入死循環(huán)。為了避免死循環(huán)，需要修改循環(huán)條件，使這些情況能夠終結(jié)。新的循環(huán)條件可能有多種選擇：while(left<right)、while(left<right-1)等等，這些循環(huán)條件的變種同時(shí)意味著循環(huán)終止時(shí)候選數(shù)組的形態(tài)。
(5)結(jié)合新的循環(huán)條件，分析終止時(shí)的候選元素的形態(tài)，并對(duì)分析要查找的下標(biāo)是否它們之中、同時(shí)是如何表示的。
對(duì)于(3)，有一些二分算法實(shí)現(xiàn)不是這樣的，它會(huì)使left或right在最后一次循環(huán)時(shí)越界，相應(yīng)的left或right是查找的目標(biāo)的最終候選，這一點(diǎn)在理解時(shí)需要注意。當(dāng)然，不利用這個(gè)思路也可以寫出能完成功能的二分查找，而且易于理解。
喜歡 
頂
難過
囧
圍觀
無(wú)聊
不错！！！！ 
