题目

思路

一句话：利用“两段单调区间”的结构，每次比较 nums[mid] 和 nums[right]，判断中点落在哪一段，从而砍掉一半。

最直白的做法是线性扫描：从左到右找到第一个“后一个比前一个小”的位置，或直接维护一个最小值。它一定正确，但需要 O(n)。本题 n 最多 5000，扫描也能过，不过题目明确要求 O(log n)，而且真正的价值是学会用二分处理“分段单调”的结构。

关键观察：旋转不会破坏每一段内部的递增关系，只会把数组切成大值段 + 小值段。最小值就是这两段的交界处。因此我们不需要逐个检查，只要判断中点现在位于哪一段：

• 若 nums[mid] > nums[right]：说明 mid 落在大值段，最小值一定在 mid 的右边。
• 否则说明 mid 已经在小值段（或数组根本没旋转），最小值在 mid 或其左边。

不断把不可能含答案的一半丢掉，区间就指数级缩小。

解法

维护区间 [left, right]，始终保持“最小值一定在这个区间内”。当 left == right 时，那个位置就是答案。

1. 取中点 mid = left + (right - left) / 2。
2. 若 nums[mid] > nums[right]，令 left = mid + 1。
3. 否则令 right = mid，注意不能写成 mid - 1，因为 nums[mid] 自己可能就是最小值。
4. 循环结束后返回 nums[left]。

以 [6,7,8,1,2,3,4] 为例：

最后 left == right == 3，返回 nums[3] == 1。

下图把上面 4 个步骤串成流程，并逐步演示：

C++

class Solution
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。