首先開始最基本的Binary Search, 數組是有序的，但是有重複數。
例題： Search for a Range
複雜度：時間O(log n), 空間O(1).
分析： 首先需要複雜度在O(log n)左右，顯然暗示了Binary Search是首選，然後注意這道題是需要找到一個range，并不是找到target的位置就可以了。
class Solution{
public:
vector searchRange(int A[], int n, int target) {
vector result(2,-1);
int index = search(A, n, target);
if(index == -1) return result;
int l = index, r = index;
while(l -1 >= 0 && A[l] == A[l-1]) --l;
while(r +1 <= n-1 && A[r] == A[r+1]) ++r;
result[0] = l;
result[1] = r;
return result;
}
int search(int A[], int n , int target){
if(A == nullptr || n == 0) return -1;
int left = 0, right = n -1;
while(left <= right){
int mid = left + (right - left) /2;
if(target > A[mid])
left = mid + 1;
else if(target < A[mid])
right = mid - 1;
else if(target == A[mid])
return mid;
}
return -1;
}
};
注意這裡做binary search時候，對于A[mid]分為了三種不同情況讨論，相等，小于和大于，并且while循環的終止條件是left <= right，也就是說最後left > right時候表明目标數肯定不存在了。在對于不同的問題，這些邊界條件會相應的改變。另外這樣搜尋如果最後目标數存在，最後結果一定是以A[mid]的形式。
例題： Search Insert Position
複雜度：時間O(log n), 空間O(1).
分析：這道題的關鍵是如果目标數不存在，必須傳回目标數可以插入的位置，這樣經典的binary search傳回A[mid]的方法(如上題)沒法直接實作是以必須對循環的條件以及邊界進行調整。首先當循環結束時候，為了能傳回一個目标數可以插入的位址，我們必須讓left == right也就是說循環條件相應調整為left < right. 如果需要設定循環裡面的邊界條件和left, right的初始條件，我們必須看一下最後一次循環時候的情況：最後一次循環時， left + 1 = right隻剩下兩個元素需要考慮(這裡忽略數組隻有一個元素的情形，因為一個元素時，程式根本不會進入循環)，此時mid = left，如果target > A[mid], left = mid + 1 = right與之前情況類似，那麼當target < A[mid]時候也就是說target并不存在，此時應該輸出target元素需要插入的位置也就是left, 是以right = mid = left，當target = A[mid]情形與小于相同，right = mid = left.還有一種情況，當target大于數組裡面所有數的時候，插入位置應該在所有數組之後，是以right的初始值必須是n，因為很容易發現前面的邊界條件設定導緻最後輸出的left都會在兩個初始值left和right之間。
本文來自電腦雜談，轉載請注明本文網址：
http://www.pc-fly.com/a/jisuanjixue/article-26574-1.html