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

二分查找，数组要么没有旋转，要么旋转成为两段局部有序的子数组。如果mid的值大于right端点的值，说明只可能是两段有序的子数组，且最小值必定出现在mid右端；如果小于，说明两种情况都可能存在，但此时最小值必定出现在mid左端；如果等于，无法判断最小值出现的区间，但是可以肯定right不会是唯一最小值（即使是最小值也有mid的值与它相同，减去没有影响），所以可以把right减一。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int l = 0, r = rotateArray.size() - 1;
        while (l < r) {
            // cout << l << " " << r << endl;
            int mid = l + (r - l) / 2;
            if (rotateArray[mid] < rotateArray[r]) r = mid;
            else if (rotateArray[mid] > rotateArray[r]) l = mid + 1;
            else r--;
        }
        return rotateArray[l];
    }
};