原創地址：http://www.cnblogs.com/segeon/archive/2012/07/27/2612361.html

很多書上都會講到二分查找（數據結構與算法教材、《編程之美》、《編程珠璣》），這也是一個經典的面試題。盡管它很常見，大家也很熟悉，但是卻不一定能夠完美地寫出來。今天自己整理了一下，把三種二分查找算法（找最后一次出現的某值v，找第一次出現的某值v和普通的二分查找）進行了梳理。

問題描述：有一個按非降序排列的有序數組a[0...n-1]和一個數v

1. 求數組a中最后一次出現的數v的下標

設l為左邊界，h為右邊界，mid =(l+h)/2，那么，根據mid的取值，分三種情況:

(1) a[mid] < v，說明v如果在數組中，應該出現在mid右側，則調整左邊界，l = mid + 1

(2) a[mid] > v，說明v如果在數組中，應該出現在mid左側，則調整右邊界，h = mid - 1

(3) a[mid] == v，中間值等于v，而要求的是最后一次出現的v。最后出現的v值一定在mid的右邊或者就是mid位置的這個值，所以我們應該調整左邊界，l = mid。

以上三步是循環體中的關鍵步驟，但容易出錯的地方不在這三步中，而在于循環結束的條件。

為了更清楚地說明問題，下面討論一下當循環體內l和h之間（包含l和h）最后只剩3個和2個元素時的情況，初始元素個數超過3個的最后都會轉化為這兩種情況之一。

只剩3個元素時，可能出現2中情況，一種是其中里面含有v，另一種是不含v。假設v = 2，那么含有v的可能出現以下幾種情況:

(1) 若v只出現一次，可能出現的最終狀態將如下圖所示：

初始狀態： ? 最終狀態 ? ，l = h

初始狀態： ? ?最終狀態 ? ??這種情況需要特別注意，因為此時l = mid,h = l + 1, 如果繼續循環，l和h的值將不會改變

初始狀態： ? 最終狀態 ? ，l = h

(2)若v出現兩次，可能出現的最終狀態如下：

初始狀態： 最終狀態 ? ， h = l + 1

初始狀態： ? ?最終狀態 ?，h = l + 1，這種情況也很特殊，因為此時l和h位置的值都是v。

(3)若v出現三次，可能出現的最終狀態如下：

初始狀態： ?最終狀態 ?，h = l + 1，此時l和h位置的值也都是v

如果數組中不含v，那么可能會出現以下兩種情況：

(1) 中間元素小于v

初始狀態： ? 最終狀態? ?， l = h

(2) 中間元素大于v

初始狀態： ?最終狀態? ??, l = h

若數組中只剩兩個元素，那么這兩個元素中可能含v，也可能不含v。如果含有v，有兩種情況：

(1) a[l] = v

初始狀態： ? 最終狀態 ? ， h = l + 1

(2) a[l] != v

初始狀態： ? ? 最終狀態 ? ， l = h

如果兩個元素中不含v，也有兩種情況：

(1) a[l] < v

初始狀態：?? ?最終狀態 ? ， l = h

(2) a[l] > v

初始狀態： 最終狀態? ?h = l - 1

從上面的分析可以得出結論，循環結束的條件應該是 l + 1< h，結束以后，需要檢查l + 1位置的值是否和v相等，相等，則l + 1是所求的位置，否則，檢查l位置的值是否和v相等，若相等，則l是所求的位置，否則，說明原數組中不存在v，返回-1。

代碼如下：

/*查找給定非遞減序列中給定關鍵字的最后一次出現的位序*/ int binarySearchLast(int *a, int l, int h, int key){if(!a || l>h)return -1;int mid;while(l+1 < h){ //循環結束條件 mid=(l+h)/2;if(a[mid] > key)h=mid-1;else if(a[mid] < key)l=mid+1;elsel=mid;}if(a[l+1] == key)return l+1;else if(a[l] == key)return l;else return -1; }

2.查找給定非遞減序列中給定關鍵字第一次出現的位序，如有返回位序，否則返回-1.

代碼如下：

/*找給定非遞減序列中給定關鍵字第一次出現的位序*/ int binarySearchFirst(int *a, int l, int h,int key){if(!a || l>h) return -1;int mid;while( l< h){ //循環結束條件 mid=(l+h)/2;if(a[mid] > key)h=mid-1;else if(a[mid] < key)l=mid+1;elsel=mid;}if(a[l] == key)return l;elsereturn -1; }

3.查找給定非遞減序列中是否存在給定關鍵字，如有返回位序，否則返回-1.

標準二分非遞歸查找。

代碼如下：

int binarySearch(int *a, int l, int h,int key){if(!a || l>h)return -1;int mid;while( l< h){ //循環結束條件 mid=(l+h)/2;if(a[mid] == key)return mid;else if(a[mid] > key)h=mid-1;elsel=mid+1;}if(a[l] == key)return l;elsereturn -1; }

另外有兩個相似的查找算法，給定一個非遞減有序數組a，求一個最小的i使得a[i]大于key，若找不到則返回-1.

貼出代碼：

/*查找給定非遞減序列中第一個大于的給定值*/ int findSmallestBiggerNumber(int *a, int l, int h, int key){if(!a || l>h)return -1;int mid;while(l < h){mid=(l+h)/2;if(a[mid] <= key)l=mid+1;elseh=mid;}if(a[l] > key)return l;elsereturn -1; }

/*給定一個非降序數組arr, 求一個最大的i使得arr[i]小于v，若找不到則返回-1*/ int findLargetSmallerNumber(int *a, int l, int h, int v) {if(!a || l > h)return -1;if(l == h){if(a[l] < v)return l;elsereturn -1;}int mid;while (l + 1 < h){mid = l + (h-l)/2;if(a[mid] >= v)h = mid - 1;elsel = mid;}if(a[l+1] < v)return l+1;if(a[l] < v)return l;return -1; }
原文地址：http://www.cnblogs.com/segeon/archive/2012/07/27/2612361.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二分查找讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

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