本文概览：本文讲解寻找旋转排序数组中的最小值的核心思路：两种方法——一次二分查找找旋转点，和一次二分查找直接找最小值

一、题目

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

二、题目分析

这题和前面的"搜索旋转排序数组"是同一类问题。

题目说数组经过旋转，每次旋转是把最后一位挪到最前面，不确定挪几次。但不管挪几次，最终结果都可以看作是左旋转了一次，即分成两段递增序列。

比如原来是 [0, 1, 2, 4, 5, 6, 7]，旋转后可能变成 [4, 5, 6, 7, 0, 1, 2]。

旋转后的数组有两个特点：

  1. 分成两段递增序列：[4, 5, 6, 7] 和 [0, 1, 2]
  2. 最小值就是旋转点

题目要求时间复杂度 O(log n)，显然要用二分查找。

有两种方法：

  1. 方法一：一次二分查找找旋转点（最小值就是旋转点）
  2. 方法二：一次二分查找直接找最小值（边找边比较）

思路概览

方法一：一次二分查找找旋转点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findMin(int[] nums) {
    if (nums.length == 1) return nums[0];
    
    // 一次二分：找旋转点（最小值的索引）
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            // 旋转点在右边
            left = mid + 1;
        } else {
            // 旋转点在左边或就是 mid
            right = mid;
        }
    }
    // 最小值就是旋转点
    return nums[left];
}

方法二：一次二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int min = nums[0];
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 如果左边有序
        if (nums[left] <= nums[mid]) {
            // 更新最小值
            min = Math.min(min, nums[left]);
            // 移动到右边
            left = mid + 1;
        }
        // 如果右边有序
        else {
            // 更新最小值
            min = Math.min(min, nums[mid]);
            // 移动到左边
            right = mid - 1;
        }
    }
    return min; 
}

思路简要说明：

方法一：

  1. 一次二分：找旋转点（最小值就是旋转点）
  2. 如果 nums[mid] > nums[right]，说明旋转点在右边；否则在左边或就是 mid

方法二：

  1. 判断哪边有序：nums[left] <= nums[mid] 说明左边有序，否则右边有序
  2. 更新最小值：有序部分的第一个元素就是这部分的候选最小值
  3. 移动：去另一边继续找，因为最小值可能在另一边

三、思路详解

方法一：两次二分查找

第一步：找旋转点

旋转点就是数组中最小值的索引。

二分时，如果 nums[mid] > nums[right]，说明旋转点在 mid 右边（因为右边有更小的值），更新 left = mid + 1。

否则旋转点在 mid 或 mid 左边，更新 right = mid。

循环结束时 left 就是旋转点。

第二步：比较两个候选最小值

旋转数组分成两段递增序列：

  • 左边序列：[0, pivot - 1]，最小值是 nums[0]
  • 右边序列：[pivot, nums.length - 1]，最小值是 nums[pivot]

比较这两个值，取较小值。

完整执行过程

以 nums = [4, 5, 6, 7, 0, 1, 2] 为例：

第一次二分：找旋转点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
初始：left=0, right=6

第 1 轮：
  mid = 3, nums[3] = 7 > nums[6] = 2
  left = 4

第 2 轮：
  left=4, right=6
  mid = 5, nums[5] = 1 <= nums[6] = 2
  right = 5

第 3 轮：
  left=4, right=5
  mid = 4, nums[4] = 0 <= nums[5] = 1
  right = 4

第 4 轮：
  left=4, right=4
  left == right，退出循环
  pivot = 4

比较

1
2
nums[0] = 4, nums[pivot] = nums[4] = 0
Math.min(4, 0) = 0 ✓

方法二：一次二分查找

第一步：判断哪边有序

和前一题一样，对于任意 mid：

  • 如果 nums[left] <= nums[mid]：说明左边有序（[left, mid] 是递增的）
  • 否则：说明右边有序（[mid, right] 是递增的）
第二步：更新最小值

情况 1：左边有序

左边有序意味着 nums[left] 是左边这部分的最小值（因为递增）。

用 nums[left] 更新 min，然后去右边继续找（left = mid + 1），因为最小值可能在右边。

情况 2：右边有序

右边有序意味着 nums[mid] 是右边这部分的最小值（因为递增）。

用 nums[mid] 更新 min，然后去左边继续找（right = mid - 1），因为最小值可能在左边。

完整执行过程

以 nums = [4, 5, 6, 7, 0, 1, 2] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
初始：left=0, right=6, min=4

第 1 轮：
  mid = 3, nums[3] = 7
  nums[0] = 4 <= nums[3] = 7 → 左边有序
  min = Math.min(4, 4) = 4
  left = mid + 1 = 4

第 2 轮：
  left=4, right=6
  mid = 5, nums[5] = 1
  nums[4] = 0 <= nums[5] = 1 → 左边有序
  min = Math.min(4, 0) = 0
  left = mid + 1 = 6

第 3 轮：
  left=6, right=6
  mid = 6, nums[6] = 2
  nums[6] = 2 <= nums[6] = 2 → 左边有序
  min = Math.min(0, 2) = 0
  left = mid + 1 = 7

第 4 轮：
  left=7, right=6
  left > right，退出循环
  返回 0 ✓

再举一个例子，nums = [3, 4, 5, 1, 2]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
初始：left=0, right=4, min=3

第 1 轮：
  mid = 2, nums[2] = 5
  nums[0] = 3 <= nums[2] = 5 → 左边有序
  min = Math.min(3, 3) = 3
  left = mid + 1 = 3

第 2 轮：
  left=3, right=4
  mid = 3, nums[3] = 1
  nums[3] = 1 > nums[3] = 1? false → 右边有序
  min = Math.min(3, 1) = 1
  right = mid - 1 = 2

第 3 轮：
  left=3, right=2
  left > right，退出循环
  返回 1 ✓

四、总结

寻找旋转排序数组中的最小值有两种方法：

方法一：两次二分查找

  1. 第一次二分找旋转点
  2. 比较 nums[0] 和 nums[pivot]，取较小值

方法二：一次二分查找

  1. 判断哪边有序
  2. 用有序部分的第一个元素更新最小值
  3. 去另一边继续找

两种方法的时间复杂度都是 O(log n)，方法二代码更简洁，但方法一思路更直观。