【LeetCode-查找】旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组?[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。??
示例：

输入：[3,4,5,1,2]
输出：1

输入：[2,2,2,0,1]
输出：0

题目链接： https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

思路

使用二分查找来做。数组可以分为两个部分，左边的元素都大于等于右边的元素。

• 初始化 left 和 right 两个指针，left = 0, right = num.size()-1;
• 如果 left<right，循环：
  • mid = (left+right)/2;
  • 如果 nums[mid]>nums[right]，说明当前 mid 在左边，则更新 left = mid+1;
  • 如果 nums[mid]<nums[left]，说明当前 mid 在右边，则更新 right = mid;
  • 如果 nums[mid]==nums[right]，此时无法判断 mid 在左边还是右边，则 right-- 缩小范围；
• 最后返回 nums[left]。

需要注意的是，我们判断 nums[mid]>nums[right]，而不是 nums[mid]>nums[left]，原因是只靠 nums[mid]>nums[left] 无法判断 mid 在左边还是在右边，而 nums[mid]>nums[right] 可以确定 mid 在哪一边；使用 nums[mid]<nums[left] 也是一样的原因。

这题我觉得难点除了上面说的判断条件之外，还有一点是这题不符合二分查找的常规写法。在常规的二分查找中，如果 right 初始化为 nums.size()-1 的话，循环条件应该是 left<=right，right的更新方式应该是 right = right-1，但这题不是，需要注意一下。

代码如下：

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size()-1;
        while(left<right){
            if(left==right) return numbers[left];
            int mid = left + (right - left) / 2;
            if(numbers[mid]>numbers[right]) left = mid + 1;
            else if(numbers[mid]<numbers[left]) right = mid;
            else right--;
        }
        return numbers[left];
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

原文：https://www.cnblogs.com/flix/p/13363038.html