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

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        // 整体思路：二分法确定拐点位置
        int len = rotateArray.size();
        int left = 0, right = len - 1;
        // 特殊情况：开头元素小于末尾元素，直接返回第一个值
        if (rotateArray[left] < rotateArray[right]) {
            return rotateArray[left];
        }
        while (left < right) {
            int mid = (right + left) / 2;
            // 前两种是找到了拐点
            if (rotateArray[mid] > rotateArray[mid + 1]) {
                return rotateArray[mid + 1];
            } else if (rotateArray[mid] < rotateArray[mid - 1]) {
                return rotateArray[mid];
            } else if (rotateArray[mid] > rotateArray[right]) {
                // 当前中间点大于最右边元素，说明左边可以削
                left = mid + 1;
            } else {
                // 左边不行，就削右边
                right = mid;
            }
        }
        return 0;
    }
};