二分查找之美：二分查找及其變體的正確性以及構造方式

二分查找究竟有多重要？《編程之美》第2.16節(jié)的最長遞增子序列算法，如果想實現(xiàn)O(n2)到O(nlogn)的時間復雜度下降，必須借助于二分算法的變形。其實很多算法都是這樣，如果出現(xiàn)了在有序序列中元素的查找，使用二分查找總能提升原先使用線性查找的算法。

然而，雖然很多人覺得二分查找簡單，但隨手寫一寫卻不能得到正確的結果：死循環(huán)、邊界條件等等問題伴隨著出現(xiàn)。《編程珠璣》第四章提到：提供充足的時間，僅有約10%的專業(yè)程序員能夠完成一個正確的二分查找。當然，正確的二分查找和變體在算法書籍以及網(wǎng)絡上隨處可得，但是如果不加以理解，如何掌握？理解時，又往往因想不清楚，一知半解，效果有限。我在看相關的變體算法時就覺得一片茫然，不得要領：或許這個算法可以這么寫，稍微變下要求就不能這么寫了；舉正例說明算法在某些情況下可以正常工作、舉反例說明算法有錯固然可行，但僅有例子是不夠的，怎樣一勞永逸地證明自己幾經修改的算法之正確？如果每一個變體都進行孤立地理解，那么太花費時間，而且效果也不好。如何解決這個問題？在思考方法和查閱書籍之后發(fā)現(xiàn)，還是要靠循環(huán)不變式來完成算法正確性的理論支撐。

或許你曾了解過循環(huán)不變式，但如果不使用的話，是看不到它的強大之處的：不僅僅能幫助你證明算法正確性，同時也幫助你理解算法，甚至能幫助你在基本算法的基礎上，構造出符合要求的相應算法變體。這些都將在后文的各個算法說明中看到。

知識準備

結合《算法導論》和《編程珠璣》，下面說明循環(huán)不變式的概念與性質。

循環(huán)不變式主要用來幫助理解算法的正確性。形式上很類似與數(shù)學歸納法，它是一個需要保證正確斷言。對于循環(huán)不變式，必須證明它的三個性質：

初始化：它在循環(huán)的第一輪迭代開始之前，應該是正確的。

保持：如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應該保持正確。

終止：循環(huán)能夠終止，并且可以得到期望的結果。

文章說明

(1)在推導每次數(shù)組減少的長度時，mid是不能代換成(left+right)/2的。這種形式代表了非整型的運算，沒有舍去小數(shù)部分，而在代碼中實際的mid是會舍去小數(shù)部分的。

(2)代碼部分的=和==意義同C語言；文字說明部分的=代表賦值，==代表等式推導或者邏輯判斷，由上下文而定。

(3)除了3和5外，最初的各個變體代碼參考于：二分查找，你真的會嗎？ 為了符合思路的前后連貫和說明循環(huán)不變式，做了一些修改。原文的測試很方便，讀者可以自行參考。

1.二分查找值為key的下標，如果不存在返回-1。

循環(huán)不變式：

如果key存在于原始數(shù)組[0,n-1]，那么它一定在[left,right]中。

初始化：

第一輪循環(huán)開始之前，處理的數(shù)組就是原始數(shù)組，這時顯然成立。

保持：

每次循環(huán)開始前，key存在于待處理數(shù)組array[left, ..., right]中。

對于array[mid]<key，array[left, ..., mid]均小于key，key只可能存在于array[mid+1, ..., right]中；

對于array[mid]>key，array[mid, ..., right]均大于key，key只可能存在于array[left, ..., mid-1]中；

對于array[mid]==key，查找到了key對應的下標，直接返回。

在前兩種情況中，數(shù)組長度每次至少減少1（實際減少的長度分別是mid-left+1和right-mid+1），直到由1（left==right）變?yōu)?（left>right），不會發(fā)生死循環(huán)。

終止：

結束時，left>right，待處理數(shù)組為空，表示key不存在于所有步驟的待處理數(shù)組，再結合每一步排除的部分數(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(可能有重復)第一次出現(xiàn)的下標x，如果不存在返回-1

循環(huán)不變式：

如果key存在于數(shù)組，那么key第一次出現(xiàn)的下標x一定在[left,right]中，且有array[left]<=key, array[right]>=key。

初始化：

第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時顯然成立。

保持：

每次循環(huán)開始前，如果key存在于原數(shù)組，那么x存在于待處理數(shù)組array[left, ..., right]中。

對于array[mid]<key，array[left, ..., mid]均小于key，x只可能存在于array[mid+1, ..., right]中。數(shù)組減少的長度為mid-left+1，至少為1。

否則，array[mid]>=key, array[mid]是array[mid, ..., right]中第一個大于等于key的元素，后續(xù)的等于key的元素（如果有）不可能對應于下標x，舍去。此時x在[left, ..., mid]之中。數(shù)組減少的長度為right-(mid+1)+1，即right-mid，根據(jù)while的條件，當right==mid時為0。此時right==left，循環(huán)結束。

終止：

此時left>=right。在每次循環(huán)結束時，left總是x的第一個可能下標，array[right]總是第一個等于key或者大于key的元素。

那么對應于left==right的情況，檢查array[left]即可獲得key是否存在，若存在則下標為x；

對于left>right的情況，其實是不用考慮的。因為left==上一次循環(huán)的mid+1，而mid<=right。若mid+1>right，意味著mid == right，但此時必有l(wèi)eft == right，這一輪循環(huá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(可能有重復)最后一次出現(xiàn)的下標x，如果不存在返回-1（模仿2的第一版）

循環(huán)不變式：

如果key存在于數(shù)組，那么key最后一次出現(xiàn)的下標x一定在[left,right]中，且有array[left]<=key, array[right]>=key。

初始化：

第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時顯然成立。

保持：

每次循環(huán)開始前，如果key存在于原數(shù)組，那么x存在于待處理數(shù)組array[left, ..., right]中。

對于array[mid]<key，array[left, ..., mid]均小于key，x只可能存在于array[mid+1, ..., right]中。數(shù)組減少的長度為mid-left+1，至少為1。

對于array[mid]==key, array[mid]是array[left, ..., mid]中最后一個值為key的元素，那么x的候選只能在array[mid, ... ,right]中，數(shù)組減少長度為mid-left。除非left == right或left == right-1，否則數(shù)組長度至少減小1。由于while的條件，只有后一種情況可能發(fā)生，如果不進行干預會陷入死循環(huán)，加入判斷分支即可解決。

對于array[mid]>key, array[mid, ..., right]均大于key，x只可能在[left, ..., mid-1]之中。數(shù)組減少的長度為(right-mid)+1，同樣至少為1。

終止：

此時left>=right,right總是從數(shù)組末尾向開始的倒序中第一個候選的x，檢查它的值是否符合要求即可。

而left總是上一輪刪掉失去x資格的元素后的第一個元素，不過這里用不到。

說明：

與上一種不同，這個算法不能簡單地根據(jù)對稱，從上一個算法直接改過來，由于整數(shù)除法總是舍棄小數(shù)，mid有時會離left更近一些。所以這種算法只是沿著上一個算法思路的改進，看上去并不是很漂亮。

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(可能有重復)最后一次出現(xiàn)的下標x，如果不存在返回-1（修改版）

根據(jù)3中的討論，可以發(fā)現(xiàn)不能直接照搬的原因是mid=(left+right)/2的舍棄小數(shù)，在left+1==right且array[left]=key時，如果不加以人為干預會導致死循環(huán)。既然最終需要干預，干脆把需要干預的時機設置為終止條件就行了。

使用while(left<right-1)可以保證每次循環(huán)時數(shù)組長度都會至少減一，終止時數(shù)組長度可能為2(left+1==right)、1(left==mid，上一次循環(huán)時right取mid==left)，但是不可能為0。(每一次循環(huán)前總有l(wèi)eft<=mid<=right，無論令left=mid還是令right=mid，都不會發(fā)生left>right)。同3一樣，right總是指向數(shù)組中候選的最后一個可能為key的下標，此時只需先檢查right后檢查left是否為key就能確定x的位置。這樣就說明了循環(huán)不變式的保持和終止，就不再形式化地寫下來了。

對于兩種情況的合并：array[mid] == key時，mid有可能是x，不能將其排除；array[mid]<key時，如果讓left = mid+1，不會違反循環(huán)不變式的條件。但是由上面的討論可知，將left=mid也是可以的，在達到終止條件前能保證數(shù)組長度單調減少。因此把兩種情況合并成最終形式。

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(可能有重復)最后一次出現(xiàn)的下標x，如果不存在返回-1（利用2的方法）

如果想最大限度地利用已有的函數(shù)，那么把需要處理的數(shù)組倒序，然后直接使用方法2，再把得到的第一次出現(xiàn)的下標做一次減法就可以得到最后一次出現(xiàn)的下標，略。

6.二分查找返回剛好小于key的元素下標x，如果不存在返回-1

如果第一反應是通過2的方法找出第一個為key的元素，返回它的下標減1，那么就錯了：這個二分查找并沒有要求key本身在數(shù)組中。

循環(huán)不變式：

如果原始數(shù)組中存在比key小的元素，那么原始數(shù)組中符合要求的元素存在于待處理的數(shù)組。

初始化：

第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時顯然成立。

保持：

每次循環(huán)開始前，x存在于待處理數(shù)組array[left, ..., right]中。

先用一個循環(huán)的條件為right>=left，違反則意味著x不存在。寫下array[mid]的比較判斷分支：

(1) array[mid]<key, 意味著x只可能在array[mid, ..., right]之間，下一次循環(huán)令left = mid，數(shù)組長度減少了(mid-1)-left+1 == mid-left，這個長度減少量只有在right-left<=1時小于1。

(2)array[mid]>=key，意味著x只可能在array[left ,... ,mid-1]之間，下一次循環(huán)令right = mid-1，同樣推導出數(shù)組長度至少減少了1。

這樣，把循環(huán)條件縮小為right>left+1，和4一樣，保證了(1)中每次循環(huán)必然使數(shù)組長度減少，而且終止時也和4的情況類似：終止時待處理數(shù)組長度只能為2或1或者空（left>right）。

終止：

 接著保持中的討論，結束時，符合的x要么在最終的數(shù)組中，要么既不在最終的數(shù)組中也不在原始的數(shù)組中（因為每一次循環(huán)都是剔除不符合要求的下標）。

數(shù)組長度為2時，right==left+1，此時先檢查right后檢查left。如果都不符合其值小于key，那么返回-1。數(shù)組長度為1時，只用檢查一次；數(shù)組長度為0時，這兩個都是無效的，檢查時仍然不符合條件。把這三種情況綜合起來，可以寫出通用的檢查代碼。反過來，根據(jù)精簡的代碼來理解這三種情況比正向地先給出直觀方法再精簡要難一些。

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的元素下標x，如果不存在返回-1

和6很類似，但如果只是修改循環(huán)中下標的改變而不修改循環(huán)條件是不合適的，下面仍要進行嚴謹?shù)恼f明和修正。

循環(huán)不變式：

如果原始數(shù)組中存在比key大的元素，那么原始數(shù)組中符合要求的元素對應下標x存在于待處理的數(shù)組。

初始化：

第一輪循環(huán)開始之前，處理的數(shù)組是[0,n-1]，這時顯然成立。

保持：

每次循環(huán)開始前，x存在于待處理數(shù)組array[left, ..., right]中。

仍然先把執(zhí)行while循環(huán)的條件暫時寫為right>=left，違反則意味著x不存在。寫下array[mid]的比較判斷分支：

(1) array[mid]<=key, 意味著x只可能在array[mid+1, ..., right]之間，下一次循環(huán)令left = mid，數(shù)組長度減少了mid-left+1，減少量至少為1。

(2)array[mid]>key，意味著x只可能在array[left ,... ,mid]之間，下一次循環(huán)令right = mid，數(shù)組長度減少了right-(mid+1)+1== right-mid，只有在right==mid時為0，此時left==right==mid。因此，循環(huán)條件必須由right>=left收縮為right>left才能避免left==right時前者會進入的死循環(huán)。

終止：

由循環(huán)的終止條件，此時left>=right。類似2的分析，left>right是不可能的，只有l(wèi)eft==right。此時檢查array[right]>key成立否就可以下結論了，它是唯一的候選元素。

補充說明：

如果是對數(shù)組進行動態(tài)維護，返回值-1可以改為length+1，表示下一個需要填入元素的位置。

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.總結：如何寫出正確的二分查找代碼？

結合以上各個算法，可以找出根據(jù)需要寫二分查找的規(guī)律和具體步驟，比死記硬背要強不少，萬變不離其宗嘛：

(1)大體框架必然是二分，那么循環(huán)的key與array[mid]的比較必不可少，這是基本框架;

(2)循環(huán)的條件可以先寫一個粗略的，比如原始的while(left<=right)就行，這個循環(huán)條件在后面可能需要修改；

(3)確定每次二分的過程，要保證所求的元素必然不在被排除的元素中，換句話說，所求的元素要么在保留的其余元素中，要么可能從一開始就不存在于原始的元素中；

(4)檢查每次排除是否會導致保留的候選元素個數(shù)的減少？如果沒有，分析這個邊界條件，如果它能導致循環(huán)的結束，那么沒有問題；否則，就會陷入死循環(huán)。為了避免死循環(huán)，需要修改循環(huán)條件，使這些情況能夠終結。新的循環(huán)條件可能有多種選擇：while(left<right)、while(left<right-1)等等，這些循環(huán)條件的變種同時意味著循環(huán)終止時候選數(shù)組的形態(tài)。

(5)結合新的循環(huán)條件，分析終止時的候選元素的形態(tài)，并對分析要查找的下標是否它們之中、同時是如何表示的。

對于(3)，有一些二分算法實現(xiàn)不是這樣的，它會使left或right在最后一次循環(huán)時越界，相應的left或right是查找的目標的最終候選，這一點在理解時需要注意。當然，不利用這個思路也可以寫出能完成功能的二分查找，而且易于理解。