序言

　　本文以經典的二分查找為例，介紹如何使用循環不變式來理解算法并利用循環不變式在原始算法的基礎上根據需要產生算法的變體。謹以本文獻給在理解算法思路時沒有頭緒而又不甘心于死記硬背的人。

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

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

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

?

知識準備

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

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

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

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

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

?

文章說明

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

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

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

?(4)根據@getgoing的提示和對原始參考代碼的回顧，mid = (left+right)/2本身可能導致溢出，比較保險的寫法是mid = left + (right-left)/2，如果想通過移位而不是除法提升速度，可以寫成mid = left + ((right-left)>>1)。 本文最初版本沒有注意到這一點，現在已經修改，這個表達式和最初的比不是很直觀，專門在這里說明。當然，在理論推導而不是程序運行時是不必考慮溢出的，mid = (left+right)/2和mid = left + (right-left)/2總是相等，因此(1)和全文中的推導并未對此修改。

?

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-left)/2;if(array[mid] < key){left = mid + 1;}else if(array[mid] > key){right = mid - 1;}elsereturn 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-left)/2;if(array[mid] < key)left = mid+1;elseright = 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-left)/2;if(array[mid] > key)right = mid - 1;else if(array[mid] == key)if(left == mid)if(array[right] == key)return right;elsereturn left;elseleft = mid;elseleft = 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-left)/2;if(array[mid] <= key)left = mid;elseright = mid;}if(array[right] == key)return right;else if(array[left] == key)return left;elsereturn -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-left)/2;if(array[mid] < key)left = mid;elseright = mid - 1;}if(array[right] < key)return right;else if(array[left] < key)return left;elsereturn -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){mid = left + (right-left)/2;if(array[mid] <= key)left = mid + 1;elseright = 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是查找的目標的最終候選，這一點在理解時需要注意。當然，不利用這個思路也可以寫出能完成功能的二分查找，而且易于理解。

?

應用：

1.查找排序數組中某個數出現的次數。(《劍指Offer》面試題38，2013.7.18更新)

解法：二分查找確定第一次和最后一次出現的下標，差值+1就是出現次數，時間復雜度O(logn).

本文轉自五岳博客園博客，原文鏈接：http://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html，如需轉載請自行聯系原作者

總結

以上是生活随笔為你收集整理的如何写出正确的二分查找？——利用循环不变式理解二分查找及其变体的正确性以及构造方式...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。