题解 | #旋转数组的最小数字#二分查找

本题肯定是想考察的二分查找的方式解决问题

二分很简单，写的时候最关键的点就是如何拿中位数去判断，二分查找的核心就是每次可以筛掉二分之一，所以重点说一下旋转数组中我们如何去拿中位数比较判断。

解题思路：

旋转数组，取右端点，和中位数比较

• 如果右端点比中位数大，则最小值一定在右半边
• 如果右端点比中位数小，则最小值一定在左半边，但是也包括中位数本身
• 如果右端点和中位数相同，这样的情况我们退一位，右端点左移一个即可，因为相同，我们也不用担心丢失最小值

偷奸耍滑写法：使用sort排了序，取第一个

c++排序（不推荐）

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(), rotateArray.end());
        return rotateArray[0];
    }
};

正经写法：二分查找

c++二分查找

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int len = rotateArray.size();
        int left=0, right=len-1, mid, min_value=rotateArray[right];
        while(left < right){      //因为是旋转数组，先取最右端的数字为target
            mid = (left + right)/2;
            if(rotateArray[mid] > min_value){  
                left = mid+1;    //中位数比右端点大，最小值肯定在右半边
            }else if(rotateArray[mid] < min_value){
                right = mid;     //中位数比右端点小，最小值肯定在左半边，但是中位数也是有可能的
            }else{
                right--;       //中位数与右端点相同，那就退一位继续执行，因为相同，退一下肯定不会丢
            }
            min_value=rotateArray[right];
        }
        return min_value;
    }
};