int binary_search(int* a, int len, int goal){
    int low = 0;
    int high = len -1;
    while (low <= high) {
        int middle = (high - low) / 2 + low; // 直接使用(high + low) / 2 可能導(dǎo)致溢出
        if (a[middle] == goal)
            return middle;
        //在左半邊
        if (a[middle] > goal)
            high = middle - 1;
        //在右半邊
        else
            low = middle + 1;
    }
    //沒(méi)找到
    return -1;
}

原理并不復(fù)雜，[low,high]構(gòu)成了潛在區(qū)間，如果中值不等于目標(biāo)，則減半對(duì)應(yīng)的區(qū)間。
有一個(gè)問(wèn)題：為什么循環(huán)條件是小于等于，而不是小于？
因?yàn)榧僭O(shè)在[1,3]中尋找2，low和high會(huì)重合，但是還不確定能否找到目標(biāo)值，循環(huán)不應(yīng)該停止。

最后的情形

因?yàn)檎麛?shù)求一般是向下取整，所以最后剩下兩三個(gè)數(shù)的時(shí)候，會(huì)有一些情況：
最后剩下兩三個(gè)數(shù)的情況

最后剩下兩個(gè)數(shù)

最后剩下三個(gè)數(shù)

思考

對(duì)于二分搜索來(lái)說(shuō)，如果找不到，每次都會(huì)移動(dòng)左邊界或右邊界，每次邊界至少會(huì)移動(dòng)1個(gè)位置，且兩個(gè)邊界每次只有一個(gè)移動(dòng)，而且移動(dòng)時(shí)不會(huì)超過(guò)另一側(cè)的邊界，那么兩邊界最終一定會(huì)相遇。每次移動(dòng)時(shí)，目標(biāo)都處于兩邊界之間(含)，所以最后兩邊界重合時(shí)，目標(biāo)只可能是兩邊界重合的位置或不存在。所以即使兩邊界重合，還要做一次判斷才可以。所以循環(huán)條件加入了等于的情況，其實(shí)如果不加等于，后續(xù)做一次判斷，也是完全可以的。

有重復(fù)值的二分查找

對(duì)于一個(gè)有序數(shù)組arr，再給定一個(gè)整數(shù)num，請(qǐng)?jiān)赼rr中找到num這個(gè)數(shù)出現(xiàn)的最左邊的位置。

給定一個(gè)數(shù)組arr及它的大小n，同時(shí)給定num。請(qǐng)返回所求位置。若該元素在數(shù)組中未出現(xiàn)，請(qǐng)返回-1。

    int findPos(vector<int> arr, int n, int num) {
        if(n==0)
            return -1;
        int left=0,right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(arr[mid]<num){
                left=mid+1;
            }else if(arr[mid]>num){
                right=mid-1;
            }else{
                right=mid;
            }
        }
        if(arr[left]==num)
            return left;
        else
            return -1;
    }

兩者最大的區(qū)別在于，如果mid指示的值等于目標(biāo)值，那么還不能確定目標(biāo)值的最左位置，但mid位置依然在我們的左右邊界內(nèi)。此時(shí)右邊界賦值為mid，而不是mid-1。因?yàn)椴荒芘懦齧id出待定區(qū)間。
這樣也會(huì)有問(wèn)題，那就是每次循環(huán)不保證一定會(huì)縮減邊界區(qū)間，會(huì)出現(xiàn)死循環(huán)。死循環(huán)發(fā)生在mid==right的情況，即left==right的時(shí)候。所以循環(huán)條件不能包括等于，而且需要在循環(huán)結(jié)束后再做一次判斷。

思考

對(duì)于二分查找來(lái)說(shuō)，我們界定一個(gè)區(qū)間，這個(gè)區(qū)間表示了目標(biāo)潛在的可能位置。每次迭代時(shí)縮減此區(qū)間，則最終當(dāng)此區(qū)間只有一個(gè)位置時(shí)，目標(biāo)要么不存在，要么一定在該位置。

局部最小值

arr中數(shù)據(jù)呈波谷狀排列，已知arr中任意兩個(gè)相鄰的數(shù)都不相等，寫(xiě)一個(gè)函數(shù)返回arr中波谷位置。
思路：對(duì)于中間值mid，需要判斷mid和左右鄰居的大小關(guān)系。如果是波谷，那么其左右鄰居一定都大于mid。同理，可以判斷是否是遞減區(qū)或遞增區(qū)，再做進(jìn)一步調(diào)整。
注意：如果波谷點(diǎn)在首尾的位置的話，立即返回首尾位置。

    int getLessIndex(vector<int> arr) {
        int len = arr.size();
        if (len == 0) return -1;
        if (len == 1) return 0;
        if (arr[0] < arr[1]) return 0;
        if (arr[len-1] < arr[len-2]) return len-1;
        int left=0,right=len-1;
        while (left <= right) {
            int mid = left+(right-left)/2;
            if (arr[mid+1] > arr[mid] && arr[mid-1] > arr[mid]) {
                return mid;
            }else if (arr[mid] > arr[mid-1]) {
                right = mid;
            }else if (arr[mid] > arr[mid+1]) {
                left = mid;
            }
        }
        return -1;
    }

循環(huán)有序數(shù)組

對(duì)于一個(gè)有序循環(huán)數(shù)組arr，返回arr中的最小值。有序循環(huán)數(shù)組是指，有序數(shù)組左邊任意長(zhǎng)度的部分放到右邊去，右邊的部分拿到左邊來(lái)。比如數(shù)組[1,2,3,3,4]，是有序循環(huán)數(shù)組，[4,1,2,3,3]也是。

    int getMin(vector<int> arr, int n) {
        if(n<=1)
            return arr[0];
        int left=0,right=n-1;
        while(left<right){
            if(arr[left]<arr[right])
                return arr[left];
            int mid=left+(right-left)/2;
            if(arr[mid]>arr[left]){
                left=mid+1;
            }else if(arr[mid]<arr[left]){
                right=mid;
            }else{
                if(arr[left]>arr[right])
                    left=mid+1;
                else{
                    int i;
                    for(i=left;i<mid;++i){
                        if(arr[i]!=arr[left])
                            break;
                    }
                    if(i==mid)
                        left=mid+1;
                    else
                        right=mid-1;
                }
                
            }
               
        }
        return arr[left];
    }

說(shuō)明：
假設(shè)本來(lái)的序列是[arr1,arr2],移動(dòng)后是[arr2,arr1].以為原始序列單調(diào)不減，所以arr1中元素小于等于arr2中元素。left是arr2的首，right是arr1的尾，所以arr[left]應(yīng)該大于等于arr[right]。否則該串并未發(fā)生交換，或者left已經(jīng)找到了最小值點(diǎn)，應(yīng)立即返回left。
對(duì)于[1,2,3,3,4]，交換后[3,4,1,2,3];對(duì)于交換后的序列，如果mid值大于等于left值，則應(yīng)處于arr1隊(duì)列；如果小于，則一定處于arr2隊(duì)列。但這其中有一個(gè)問(wèn)題，如果left和right和mid值都相等，那么就無(wú)法判斷了。比如[1 2 2 2 2 2]->[2 1 2 2 2 2]->[2 2 2 2 1 2]首尾以及mid都是2，但是1可能在arr1和arr2是不確定的。這種情況arr1和arr2中一定有一個(gè)全部元素相等的序列，只需對(duì)其中一個(gè)序列進(jìn)行遍歷來(lái)判斷即可。
所以策略如下：

• 如果left值小于right，則返回left。此時(shí)表示最小值已找到。
• 如果mid值大于left，則mid應(yīng)處于arr2序列?？s減左邊界至mid后一位
• 如果mid值大于right，則mid應(yīng)處于arr1序列?？s減右邊界至mid前一位
• 如果mid值等于left，判斷l(xiāng)eft和right值是否相等。
  • 若否，則mid應(yīng)處于arr2序列，縮減左邊界至mid后一位
  • 若是，則需遍歷[left,mid],判斷其是否是全等序列，再調(diào)整區(qū)間邊界。

關(guān)于終止條件

如果[4 1 2]的情況，判定mid屬于arr1序列，會(huì)縮減左邊界，此時(shí)是[1 2],這時(shí)候會(huì)觸發(fā)終止條件。所以在決定終止條件的時(shí)候，需要想清楚最終可能的情況。