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

1.使用二分查找

具体做法：

• step 1：双指针指向旋转后数组的首尾，作为区间端点。
• step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。
• step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。
• step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。
• step 5：通过调整区间最后即可锁定最小值所在。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size()-1;
        while(left < right)
        {
            int mid = (left + right)/2;
            //若是区间中点值大于区间右界值，则最小的数字一定在中点右边
            if(rotateArray[mid] > rotateArray[right])
                left = mid + 1;
            //若是区间中点值小于区间右界值，则最小的数字一定在中点左边
            else if(rotateArray[mid] < rotateArray[right])
                right = mid;
            //若是区间中点值等于区间右界值，则不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界
            else
                right--;  
        }
        return rotateArray[left];
    }
};