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

问题描述

给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按照下面的情形进行了多次旋转：

旋转操作：将数组最前面的元素取出并放到数组的末尾。例如，原数组 [0,1,2,4,5,6,7] 旋转一次后变成 [1,2,4,5,6,7,0]。

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]，若旋转 7 次（即数组长度），则可以得到原数组 [0,1,2,4,5,6,7]。

请你找出并返回数组中的最小元素。

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

示例

示例 1：

1
2
3

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

1
2
3

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次（整个长度）得到输入数组。

约束条件

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

对于这道题，我们首先要理解旋转排序数组的特性：

如果数组进行了旋转，那么它会被分成两个升序子数组
最小值是第二个子数组的第一个元素
如果数组旋转了n次（相当于没旋转），则第一个元素就是最小值

由于题目要求O(log n)的时间复杂度，二分查找是最自然的选择。

解法一：传统二分查找

核心思路

传统二分查找的关键是确定最小值在哪个区间。我们可以通过比较中间元素和右边界元素来判断：

如果 nums[mid] < nums[right]：说明 [mid, right] 这一段是有序的，最小值在 mid 或其左侧
如果 nums[mid] > nums[right]：说明最小值在 mid 右侧

实现细节

初始化左右边界 left = 0, right = n-1
当 left < right 时执行循环
计算中间位置 mid = (left + right) / 2
比较 nums[mid] 和 nums[right]
- 如果 nums[mid] < nums[right]：更新 right = mid
- 如果 nums[mid] > nums[right]：更新 left = mid + 1
循环结束后，left 指向的就是最小值的位置

代码实现

func findMin(nums []int) int {
	n := len(nums)
	left, right := 0, n-1
	
	for left < right {
		mid := (left + right) >> 1 // 等价于 mid := (left + right) / 2
		
		if nums[mid] < nums[right] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	
	return nums[left]
}

执行过程模拟

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

初始：left = 0, right = 6
第一次迭代：
- mid = 3, nums[mid] = 7, nums[right] = 2
- 7 > 2，所以 left = mid + 1 = 4
第二次迭代：
- left = 4, right = 6
- mid = 5, nums[mid] = 1, nums[right] = 2
- 1 < 2，所以 right = mid = 5
第三次迭代：
- left = 4, right = 5
- mid = 4, nums[mid] = 0, nums[right] = 1
- 0 < 1，所以 right = mid = 4
此时 left = right = 4，循环结束，返回 nums[4] = 0，这是正确的最小值

解法二：使用 Go 的 sort.Search

Go 的 sort.Search 函数实现原理

sort.Search 是 Go 标准库中的二分查找实现，它寻找满足特定条件的最小索引。其实现原理如下：

func Search(n int, f func(int) bool) int {
    // 定义搜索区间 [0, n)
    lo, hi := 0, n
    // 当搜索区间不为空时继续
    for lo < hi {
        // 计算中间点
        mid := lo + (hi-lo)/2
        // 如果条件满足，说明结果在左半部分 [lo, mid]
        if f(mid) {
            hi = mid
        } else {
            // 否则结果在右半部分 (mid, hi)
            lo = mid + 1
        }
    }
    // lo 是第一个满足条件的索引，如果不存在则等于 n
    return lo
}

sort.Search 函数有两个核心特性：

它返回第一个使得条件函数 f(i) 返回 true 的索引 i
如果所有元素都不满足条件，它会返回 n（搜索范围的上限）

核心思路

在旋转排序数组中，如果我们寻找第一个小于 nums[0] 的元素，那么：

如果数组经过旋转，这个元素就是最小值
如果找不到这样的元素（即 sort.Search 返回数组长度），说明数组没有旋转或旋转了整个长度，此时 nums[0] 就是最小值

代码实现

func findMin(nums []int) int {
	index := sort.Search(len(nums), func(i int) bool {
		return nums[i] < nums[0]
	})

	if index >= len(nums) {
		return nums[0]
	}

	return nums[index]
}

执行过程模拟

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

我们寻找第一个小于 nums[0] = 4 的元素
初始：lo = 0, hi = 7
第一次迭代：
- mid = 3, nums[mid] = 7
- 7 < 4 ? 否，所以 lo = mid + 1 = 4
第二次迭代：
- lo = 4, hi = 7
- mid = 5, nums[mid] = 1
- 1 < 4 ? 是，所以 hi = mid = 5
第三次迭代：
- lo = 4, hi = 5
- mid = 4, nums[mid] = 0
- 0 < 4 ? 是，所以 hi = mid = 4
此时 lo = hi = 4，循环结束，返回 lo = 4
因为 index = 4 < len(nums) = 7，所以返回 nums[4] = 0，这是正确的最小值

对于 nums = [11,13,15,17]（没有旋转）：

我们寻找第一个小于 nums[0] = 11 的元素
经过二分查找，发现没有元素小于 11
sort.Search 返回 index = 4（数组长度）
因为 index >= len(nums)，所以返回 nums[0] = 11，这是正确的最小值

边界情况分析

解法一的边界处理

为什么我们在解法一中比较中间值和右边界值，而不是左边界值？这是因为：

如果比较中间值和左边界值，在某些情况下无法确定最小值在哪一侧
- 例如，在 [3,4,5,1,2] 中
  - nums[mid=2] = 5, nums[left=0] = 3，5 > 3，但最小值在右侧
- 例如，在 [5,1,2,3,4] 中
  - nums[mid=2] = 2, nums[left=0] = 5，2 < 5，但最小值在左侧
而比较中间值和右边界值可以明确判断：
- 如果 nums[mid] < nums[right]：[mid, right] 是有序的，最小值在 mid 或其左侧
- 如果 nums[mid] > nums[right]：最小值一定在 mid 右侧

终止条件 left == right 确保了我们能够找到最小值的确切位置。

二分查找边界条件的精确选择

在这道题的二分查找实现中，边界条件的选择尤为关键：

为什么使用 left < right 而不是 left <= right？
- 使用 left < right 意味着当 left == right 时循环终止
- 此时搜索区间缩小到只有一个元素，这个元素就是最小值
- 如果使用 left <= right，当 left == right 时，mid 也等于 left 和 right
- 如果进入 right = mid 的分支，搜索区间不会缩小，导致死循环
为什么使用 right = mid 而不是 right = mid - 1？
- 当 nums[mid] < nums[right] 时，说明 [mid, right] 这一段是有序的
- 此时最小值可能是 mid（如果 mid 刚好是最小值的位置）
- 如果使用 right = mid - 1，当 mid 是最小值时，我们会错过它
- 例如：在 [4,5,1,2,3] 中，当 left=0, right=4, mid=2 时，nums[mid]=1 < nums[right]=3
- 如果使用 right = mid - 1，会把搜索范围缩小到 [0,1]，从而错过最小值 1
为什么使用 left = mid + 1 而不是 left = mid？
- 当 nums[mid] >= nums[right] 时，说明 mid 不可能是最小值
- 最小值一定在 mid 的右侧，所以可以安全地使用 left = mid + 1
- 如果使用 left = mid，当 left 和 right 相邻时（例如 left=4, right=5），
- 计算得到 mid=4，如果进入 left = mid 分支，left 仍然是 4，搜索区间不变
- 这会导致算法陷入死循环

这些边界条件的精确选择，确保了算法既能正确找到最小值，又能高效地收敛而不会陷入死循环。

解法二的边界处理

解法二的边界处理体现在：

1
2
3

if index >= len(nums) {
	return nums[0]
}

这个判断是为了处理数组没有旋转或旋转了整个长度（等价于没旋转）的情况。在这种情况下，没有元素小于 nums[0]，sort.Search 会返回数组长度 n，此时 nums[0] 就是最小值。

sort.Search 函数的边界设计

Go 语言的 sort.Search 函数有其独特的边界处理机制：

搜索区间是半开区间 [0, n)
- 注意右边界是 n 而不是 n-1
- 这样设计的好处是，当所有元素都不满足条件时，返回值为 n
- 我们可以通过检查 index >= len(nums) 来捕获这种情况

内部循环使用 lo < hi

// sort.Search 的简化实现
func Search(n int, f func(int) bool) int {
    lo, hi := 0, n
    for lo < hi {
        mid := lo + (hi-lo)/2
        if f(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

当 lo == hi 时退出循环，确保搜索会收敛到一个确定的位置
lo 最终指向第一个满足条件的元素，或者指向 n（如果没有满足条件的元素）

边界更新规则
- 如果 f(mid) 为 true，则 hi = mid（不是 mid-1）
- 这确保了找到的是第一个满足条件的元素
- 如果 f(mid) 为 false，则 lo = mid + 1（不是 mid）
- 这确保了循环会终止，避免死循环

对于我们的问题，条件函数是 nums[i] < nums[0]，表示从数组中找到第一个小于 nums[0] 的元素。这种边界设计使得 sort.Search 非常适合查找第一个满足某条件的元素，在旋转排序数组中找最小值的场景下尤为优雅。

对于边缘情况，如数组只有一个元素：

解法一：left = 0, right = 0，循环不会执行，直接返回 nums[0]
解法二：没有元素小于 nums[0]，sort.Search 返回 1，执行 if index >= len(nums)，返回 nums[0]

复杂度分析

两种解法的复杂度分析：

时间复杂度：两种解法都是 $O(\log n)$，因为它们都使用了二分查找，每次将搜索空间减半

空间复杂度：两种解法都是 $O(1)$，只使用了常数额外空间

解法比较

方面	解法一（传统二分）	解法二（sort.Search）
时间复杂度	$O(\log n)$	$O(\log n)$
空间复杂度	$O(1)$	$O(1)$
优点	更加直观，不依赖库函数	代码更简洁，利用了Go语言特性
缺点	需要手动实现二分查找	需要理解sort.Search函数的特性
适用场景	各种语言环境	Go语言环境

关键收获

二分查找的比较策略很重要：在旋转排序数组中，选择合适的比较策略（与左边界或右边界比较）会直接影响算法的正确性
利用语言特性可以简化代码：Go语言的 sort.Search 函数提供了一种简洁的二分查找实现方式
理解问题结构是关键：理解旋转排序数组的结构特点（两个有序子数组）有助于设计高效算法
边界情况的处理至关重要：特别注意数组未旋转或只有一个元素的情况

这道题展示了如何利用二分查找高效解决旋转排序数组问题，以及如何灵活运用语言特性简化代码实现。