153 寻找旋转排序数组中的最小值

一、题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二、题解

方法一：二分查找（和右边界比较）

思路：使用二分查找。

1. 核心思路

旋转排序数组可以看成由两段递增数组组成。

例如：

[4,5,6,7,0,1,2]

可以分成：

[4,5,6,7] 和 [0,1,2]

最小值一定出现在第二段递增数组的开头，也就是旋转点。

核心思想是：

  • 使用 left 和 right 表示当前查找区间；
  • 每次取中间位置 mid；
  • 比较 nums[mid] 和 nums[right]，判断最小值在左边还是右边。

2. 具体步骤

  1. 定义两个指针：

    • left = 0
    • right = nums.length - 1

  2. 当 left < right 时，持续二分查找。

  3. 计算中间位置：

int mid = left + (right - left) / 2;

  1. 判断 nums[mid] 和 nums[right] 的大小关系：

    • 如果 nums[mid] > nums[right]：

      • 说明 mid 在左边较大的递增区间；
      • 最小值一定在 mid 的右边；
      • 所以令 left = mid + 1。

    • 如果 nums[mid] < nums[right]：

      • 说明 mid 可能就是最小值；
      • 或者最小值在 mid 左边；
      • 所以令 right = mid。

  2. 当循环结束时，left == right，此时指向的位置就是最小值。

3. 关键逻辑

if (nums[mid] > nums[right]) {
    left = mid + 1;
} else {
    right = mid;
}

解释：

  • 如果 nums[mid] > nums[right]，说明中间值比右边界还大，最小值一定在右半部分；
  • 所以更新 left = mid + 1；
  • 否则说明 mid 到 right 这一段是递增的，最小值可能是 nums[mid]，也可能在左边；
  • 所以更新 right = mid，不能写成 right = mid - 1，因为 mid 可能就是答案。

4. 代码

class Solution {
    public int findMin(int[] nums) {
        // 1. 定义左右边界
        int left = 0;
        int right = nums.length - 1;

        // 2. 二分查找最小值位置
        while (left < right) {
            int mid = left + (right - left) / 2;

            /*
             * 如果 nums[mid] > nums[right]
             * 说明 mid 在左边较大的递增区间
             * 最小值一定在 mid 右边
             */
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } 
            /*
             * 否则说明 nums[mid] <= nums[right]
             * 因为题目中元素互不相同，所以这里实际上是 nums[mid] < nums[right]
             * 最小值可能是 nums[mid]，也可能在 mid 左边
             */
            else {
                right = mid;
            }
        }

        // 3. left 和 right 相遇的位置就是最小值
        return nums[left];
    }
}

5. 复杂度分析

时间复杂度：O(log⁡n)O(\log n)

说明：每次都会排除一半的查找区间，所以时间复杂度是 O(log⁡n)O(\log n)。

空间复杂度：O(1)O(1)

说明：只使用了 left、right、mid 等常数级变量。

方法二：二分查找（和左边界比较）

思路：使用二分查找。

1. 核心思路

方法一是通过比较 nums[mid] 和 nums[right] 来判断最小值的位置。

方法二可以换一个角度：

  • 原数组是升序数组；
  • 旋转之后，如果数组没有真正发生变化，那么第一个元素就是最小值；
  • 如果发生了旋转，那么最小值一定是第一个小于 nums[0] 的元素。

例如：

[4,5,6,7,0,1,2]

这里 nums[0] = 4。

第一个小于 4 的元素是 0，所以 0 就是最小值。

2. 具体步骤

  1. 如果数组本身已经有序，即：
nums[0] < nums[nums.length - 1]

说明没有旋转，直接返回 nums[0]。

  1. 定义左右边界：
int left = 0;
int right = nums.length - 1;

  1. 在区间中二分查找第一个小于 nums[0] 的元素。

  2. 判断 nums[mid] 和 nums[0] 的关系：

    • 如果 nums[mid] >= nums[0]：

      • 说明 mid 还在左边较大的递增区间；
      • 最小值一定在右边；
      • 所以令 left = mid + 1。

    • 如果 nums[mid] < nums[0]：

      • 说明 mid 已经进入右边较小的递增区间；
      • mid 可能就是最小值；
      • 所以令 right = mid。

  3. 最后返回 nums[left]。

3. 关键逻辑

if (nums[mid] >= nums[0]) {
    left = mid + 1;
} else {
    right = mid;
}

解释：

  • 如果 nums[mid] >= nums[0]，说明 mid 还在旋转点左侧；
  • 最小值一定不在 mid 及其左侧，所以移动 left；
  • 如果 nums[mid] < nums[0]，说明 mid 已经在旋转点右侧；
  • mid 可能就是第一个较小的元素，所以移动 right 到 mid。

4. 代码

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;

        // 1. 如果数组本身就是升序的，直接返回第一个元素
        if (nums[0] < nums[n - 1]) {
            return nums[0];
        }

        // 2. 定义左右边界
        int left = 0;
        int right = n - 1;

        // 3. 二分查找第一个小于 nums[0] 的元素
        while (left < right) {
            int mid = left + (right - left) / 2;

            /*
             * 如果 nums[mid] >= nums[0]
             * 说明 mid 还在左边较大的递增区间
             * 最小值一定在 mid 右边
             */
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } 
            /*
             * 如果 nums[mid] < nums[0]
             * 说明 mid 已经在右边较小的递增区间
             * mid 可能就是最小值
             */
            else {
                right = mid;
            }
        }

        // 4. left 指向第一个小于 nums[0] 的元素，也就是最小值
        return nums[left];
    }
}

5. 复杂度分析

时间复杂度：O(log⁡n)O(\log n)

说明：每次二分都会缩小一半查找范围。

空间复杂度：O(1)O(1)

说明：只使用了常数级变量。

评论