题解 | #旋转数组的最小数字# 二分法

// leetcode里似乎见过这个
// 和BM19 寻找峰值 是相通的
class Solution {
public:

    // 
    int minNumberInRotateArray(vector<int> rotateArray) {

        int n = rotateArray.size();

        int left = 0, right = n-1;

        while(left<right)
        {
            int mid = (right+left)/2;
            
            if(rotateArray[mid]>rotateArray[right]) // 都跟最右侧指针的值比较 
            {
                left = mid+1; // mid 位于前面 最小值一定在右侧
            }
            else if (rotateArray[mid]<rotateArray[right])
            {
                right = mid; // 最小值可能是它 也可能左侧
            }
            else // 注意 相邻两个元素可能是相等的
            {
                // [mid] == [n-1]
                right--; // 两者都有可能

            }
        }

        return rotateArray[right];

        
    }
};