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

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

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

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

知識準備

結合《算法導論》和《程式設計珠玑》，下面說明循環不變式的概念與性質。

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

初始化：它在循環的第一輪疊代開始之前，應該是正确的。

保持：如果在循環的某一次疊代開始之前它是正确的，那麼，在下一次疊代開始之前，它也應該保持正确。

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

文章說明

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

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

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

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

循環不變式：

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

初始化：

第一輪循環開始之前，處理的數組就是原始數組，這時顯然成立。

保持：

每次循環開始前，key存在于待處理數組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對應的下标，直接傳回。

在前兩種情況中，數組長度每次至少減少1（實際減少的長度分别是mid-left+1和right-mid+1），直到由1（left==right）變為0（left>right），不會發生死循環。

終止：

結束時，left>right，待處理數組為空，表示key不存在于所有步驟的待處理數組，再結合每一步排除的部分數組中也不可能有key，是以key不存在于原數組。

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(可能有重複)第一次出現的下标x，如果不存在傳回-1

循環不變式：

如果key存在于數組，那麼key第一次出現的下标x一定在[left,right]中，且有array[left]<=key, array[right]>=key。

初始化：

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

保持：

每次循環開始前，如果key存在于原數組，那麼x存在于待處理數組array[left, ..., right]中。

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

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

終止：

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

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

對于left>right的情況，其實是不用考慮的。因為left==上一次循環的mid+1，而mid<=right。若mid+1>right，意味着mid == right，但此時必有left == right，這一輪循環從開始就不可能進入。

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(可能有重複)最後一次出現的下标x，如果不存在傳回-1（模仿2的第一版）

循環不變式：

如果key存在于數組，那麼key最後一次出現的下标x一定在[left,right]中，且有array[left]<=key, array[right]>=key。

初始化：

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

保持：

每次循環開始前，如果key存在于原數組，那麼x存在于待處理數組array[left, ..., right]中。

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

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

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

終止：

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

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

說明：

與上一種不同，這個算法不能簡單地根據對稱，從上一個算法直接改過來，由于整數除法總是舍棄小數，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(可能有重複)最後一次出現的下标x，如果不存在傳回-1（修改版）

根據3中的讨論，可以發現不能直接照搬的原因是mid=(left+right)/2的舍棄小數，在left+1==right且array[left]=key時，如果不加以人為幹預會導緻死循環。既然最終需要幹預，幹脆把需要幹預的時機設定為終止條件就行了。

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

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

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(可能有重複)最後一次出現的下标x，如果不存在傳回-1（利用2的方法）

如果想最大限度地利用已有的函數，那麼把需要處理的數組倒序，然後直接使用方法2，再把得到的第一次出現的下标做一次減法就可以得到最後一次出現的下标，略。

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

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

循環不變式：

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

初始化：

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

保持：

每次循環開始前，x存在于待處理數組array[left, ..., right]中。

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

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

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

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

終止：

 接着保持中的讨論，結束時，符合的x要麼在最終的數組中，要麼既不在最終的數組中也不在原始的數組中（因為每一次循環都是剔除不符合要求的下标）。

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

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很類似，但如果隻是修改循環中下标的改變而不修改循環條件是不合适的，下面仍要進行嚴謹的說明和修正。

循環不變式：

如果原始數組中存在比key大的元素，那麼原始數組中符合要求的元素對應下标x存在于待處理的數組。

初始化：

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

保持：

每次循環開始前，x存在于待處理數組array[left, ..., right]中。

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

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

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

終止：

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

補充說明：

如果是對數組進行動态維護，傳回值-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.總結：如何寫出正确的二分查找代碼？

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

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

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

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

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

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

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