【剑指offer T11】旋转数组的最小数字

参考解答区“leetcold”的解答，进行图示分析

分析：二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。

• 处于递增：low上移

• 处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）

• 其余情况：low++缩小范围
  

• 特殊情况：

代码：

int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.empty())
            return 0;

        int low = 0;
        int high = rotateArray.size() - 1;
        int mid = 0;

        while(low < high){
            // 子数组是非递减的数组，10111
            if (rotateArray[low] < rotateArray[high]) 
                return rotateArray[low];
            mid = low + (high - low) / 2;
            if(rotateArray[mid] > rotateArray[low])
                low = mid + 1;
            else if(rotateArray[mid] < rotateArray[high])
                high = mid;
            else low++;
        }
        return rotateArray[low];
    }