解题思路

二分法。

• 如果中点处的值大于右边界的值，则最小值在中点右边，更新左边的边界；
• 如果中点处的值小于右边界的值，则最小值在中点的左边或者是中点，更新右边界的值；
• 如果相等的话，则逐步向左减少右边界的值。
• 最终返回结果即可。

复杂度

• 时间复杂度为O（logn）；
• 空间复杂度为O（1）。

代码

Python

class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (right+left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] == nums[right]:
                right -= 1
            else:
                right = mid

        return nums[left]

C++

class Solution {
public:
    int minNumberInRotateArray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

        while(left < right)
        {
            int mid = int((left+right) / 2);
            if(nums[mid] > nums[right])
            {
                left = mid+1;
            }
            else if(nums[mid] < nums[right])
            {
                right = mid;
            }
            else {
                right--;
            }
        }

        return nums[left];
    }
};