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

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(rotateArray[mid] > rotateArray[right]) 
                left = mid + 1;
            //无法判断，一个一个试
            else if(rotateArray[mid] == rotateArray[right]) 
                right--;
            //最小数字要么是mid要么在mid左边
            else 
                right = mid;
        }
        // 最终left应该等于right，所在return rotateArray[left] 或 rotateArray[right]都行;
        // return rotateArray[left];
        return rotateArray[right];
    }
};


// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param nums int整型vector 
//      * @return int整型
//      */
//     int minNumberInRotateArray(vector<int>& nums) {
//         // write code here
//         // 旋转后数组变成两部分非降序数组
//         // 二分查找

//         // 补充：特殊情况
//         if (nums.size()== 0) {
//             return 0;
//         }

//         int left=0, right=nums.size()-1;

//         while(left<right)
//         {
//             // 找到数组的中点 m
//             int mid = (right+left)>>1;

//             // m在左排序数组中，旋转点在 [mid+1, right] 中
//             if(nums[mid]>nums[right])
//                 left = mid+1;
//             // m 在右排序数组中，旋转点在 [left, mid]中
//             else if(nums[mid]<nums[right])
//                 right = mid;
//             // 缩小范围继续判断
//             else
//                 --right;
//         }

//         return nums[left];
//     }
// };