二分搜索及其擴展（循環遞增數組的搜索）

二分搜索需要注意開閉區間的問題，限制條件和邊界要保持配對：low<=high ， low = mid +1 ，high = mid-1。
二分搜索的模板如下：

1. // 二分搜索
2. int BinarySearch(int *num, int key, int low, int high)
3. {
4. int mid ;
5. while(low <= high) //切記：條件是 <= ，很多次都不小心寫成了 < ，導致了N多WA
6. {
7. mid = (low + high)>>1;
8. if(num[mid] == key)
9. return mid;
10. else if(num[mid] < key)
11. low = mid + 1;
12. else
13. high = mid -1;
14. }
15. return low; //查找不成功時，返回應該插入的位置，或者直接返回-1，表示查找失敗也是可以的
16. }

二分搜索的擴展：對已排好序的數組A，一般來說可用二分查找 可以很快找到。現有一特殊數組A[]，它是循環遞增的，如A[]={ 17 19 20 25 1 4 7 9}，試在這樣的數組中找一元素x，看看是否存在。請寫出你的算法，必要時可寫偽代碼，並分析其空間、時間復雜度。

對於循環有序的數組，它是循環遞增的，例如：A[]={ 17 19 20 25 1 4 7 9}，也可以使用二分搜索：每次將數組分為2部分，一個是單調遞增的，一個是循環遞增的。如果是單調遞增的話直接使用樸素的二分搜索，如果是循環遞增的話繼續使用特殊二分搜索下去。

思路分析：

在一個數組中檢索一個元素，最普通的算法就是時間復雜度為O(n)的順序檢索。要降低時間復雜度，並結合循環遞增數組的元素已有一定程度順序的性質，很容易想到二分查找。

我最初的想法是：樸素的二分查找在是下標區間[0 n-1]內進行二分，那麼利用循環遞增的性質，我們可以在數組的有效下標區間[0 n-1]的一個偏移區間[r+1 n+r-1]裡進行二分（其中r是上述循環遞增數組定義中的那個分界下標r）。但是，這個想法的一個最大問題是：給定一個循環遞增數組，我如何去確定其分界下標r？最明顯的做法就是順序掃描一遍數組，然後確定其分界下標r。但是，既然你都掃描一遍了，也就能確定檢索元素是否在該數組中了，何必再去利用分界下標r去檢索呢？

上述想法不成功，我們再去深入地去思考二分查找方法的一些原理特性。在一個嚴格遞增的數組中，我們將要檢索的元素和數組中間的元素進行比較，然後根據要檢索的元素與數組中間的元素的大小關系來確定該元素落在那個范圍內，然後遞歸地在該范圍內進行檢索。

現在在循環遞增數組中，我們不能簡單地通過與數組中間元素的大小關系來確定要檢索的元素所落在的區間范圍。要確定范圍，我們可以再加上要檢索的元素與數組兩端的元素的大小關系。

循環遞增數組有這麼一個性質：以數組中間元素將循環遞增數組劃分為兩部分，則一部分為一個嚴格遞增數組，而另一部分為一個更小的循環遞增數組。當中間元素大於首元素時，前半部分為嚴格遞增數組，後半部分為循環遞增數組；當中間元素小於首元素時，前半部分為循環遞增數組；後半部分為嚴格遞增數組。

記要檢索的元素為key，數組的首元素為a[low]，中間元素為a[mid]，末尾元素為a[high]。則當key不等於a[mid] 時，

1、a[mid] > a[low]，即數組前半部分為嚴格遞增數組，後半部分為循環遞增數組時，若key小於a[mid]並且不小於a[low]時，則key落在數組前半部分；否則，key落在數組後半部分。

2、a[mid] < a[high]，即數組前半部分為循環遞增數組，後半部分為嚴格遞增數組時，若key大於a[mid]並且不大於a[high]時，則key落在數組後半部分；否則，key落在數組前半部分。