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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        // write code here
        // 将旋转之后位于右边的数组称为右边数组，左边数组称为左边数组。右边数组的第一个元素即为最小值。如果将0个元素进行旋转，则整个数组均为右边数组部分。
        int l = 0;
        int r = nums.size()-1;
        //待查区间[l, r]. 
        int n = nums.size();
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] < nums[r])
            {
                //最小值元素一定位于mid或者mid左边
                r = mid;  
            }
            else if (nums[mid] > nums[r]) {
                //最小值元素一定位于mid右边
                l = mid + 1; // l-1位置一定位于最小值左边
            }
            else{
                r = r - 1; //最小值元素位置不确定。可以确定的是去掉nums[r]不会错过最小值元素。因为nums[mid] == nums[r]. 如果nums[r]是最小值元素，则nums[mid]仍然在搜索区间内。如果r = mid, 则r + 1即为最终元素。

            }
            // 最后l = r + 1. 

        }
        return nums[r+1];
    }
};