复杂度与二分搜索
1. 什么是 \(O(n)\) 和 \(O(\log n)\)？
先看一段最简单的 Python 代码：
for i in range(x):
# do something
这段代码的意思是：
把同一件事情重复做 x 次。
所以如果：
x = 10→ 做 10 次x = 100→ 做 100 次x = 1,000,000→ 做 1,000,000 次
你可以这样理解：
输入变大多少倍，工作量就变大多少倍。
这种增长方式，我们叫做：
更严谨一点的说法
这里的 n 并不是代码里的某个变量名，而是：输入的规模（input size）
比如：
nums = [3, 1, 5, 2]
for i in range(len(nums)):
# 做一件事情
这段代码会：
- 有 4 个元素 → 做 4 次
- 有 100 个元素 → 做 100 次
所以：操作次数 \(\propto\) 输入大小，这就是 \(O(n)\)。
2. 那什么是 \(O(\log n)\)？
现在换一个思路。
不要一个一个检查，而是每一步都直接排除一半的可能性。
举个非常直观的例子：假设你在猜一个 1 到 100 之间的数字，你可以这样猜：
- 第一次猜 50 → 一下排掉一半
- 如果答案更小 → 只剩 1–49
- 再猜 25 → 又排掉一半
- 再猜 12 → 再排一半
- 再猜 6 → 再排一半
- 再猜 3 → 再排一半
- 再猜 1
整个过程是：
100 → 50 → 25 → 12 → 6 → 3 → 1
你只用了 大约 7 步。如果你用最笨的方法：一个一个试 → 最多要试 100 次；如果你每次砍一半：只需要 7 次左右。再看更大的数据，如果输入变大：
n = 10→ 大约 4 步n = 100→ 大约 7 步n = 1,000,000→ 大约 20 步
注意这里很关键的一点：
输入变成 10000 倍，步骤只多了一点点。
这种增长方式，我们叫：
3. 什么是 Binary Search（二分查找）？
刚才“猜数字”的过程，其实就是一种算法，叫做：
Binary Search（二分查找）
核心思想只有一句话：每一步都把可能的范围缩小一半。用更通俗的话说，不是“找答案”，而是不断缩小范围，直到只剩一个答案。
4. 我只是想知道这道题该怎么做，能不能不要讲这么多？
这题的核心其实非常短：
把最小值看成一个“谷底”，然后用二分去判断这个谷底在左边还是右边。
题目说，一个序列是 unimodal，意思是：
- 前半段一直在下降
- 后半段一直在上升
所以它的形状大概像这样：
9 7 5 3 4 6 8
^
最小值
也就是说，这个数组一定像一个 V 字形，或者至少像“先往下走，再往上走”。
注意题目还说了：
decreasing part 或 increasing part 可以是空的。
这句话很重要，因为它说明：
[1,2,3]也合法（只有上升，没有下降）[4,3,2,1]也合法（只有下降，没有上升）
所以你不能写一个只适用于“标准 V 字形”的奇怪特判代码，最好写一个统一处理所有情况的方法。
5. 为什么这题可以二分？
关键在于：我们并不需要“检查整个数组”，而是只需要看中间附近的趋势。
设中间位置是 mid，那么只看：
nums[mid]
nums[mid + 1]
就够了。
为什么？因为如果：
nums[mid] > nums[mid + 1]
说明你现在还在往下走，也就是说最小值一定在 右边。
例如：
9 7 5 3 4 6 8
^
mid = 5
这里 5 > 3，说明还没走到谷底，所以应该往右找。
反过来，如果：
nums[mid] < nums[mid + 1]
说明你现在已经开始往上走了，那最小值一定在 mid 或它左边。
所以我们就得到了二分规则：
- 如果
nums[mid] > nums[mid + 1]，令left = mid + 1 - 否则，令
right = mid
每次都能丢掉一半区间，这就是标准的 \(O(\log n)\)。
6. 这个规则为什么不会错？
你可以把数组想成一条山谷曲线。
在谷底左边，数组是下降的：
8 6 4 2
所以会出现：
nums[mid] > nums[mid + 1]
在谷底右边，数组是上升的：
2 3 5 7
所以会出现：
nums[mid] < nums[mid + 1]
也就是说，比较 mid 和 mid + 1，其实在问：
你现在是在谷底左边，还是谷底右边？
一旦这个问题能回答，我们就能把不可能包含答案的一半直接删掉。这就是为什么这题适合用 binary search。
7. 边界情况怎么办？
其实这个写法很自然地就把边界情况都处理掉了。
情况 1：整个数组一直上升
比如：
1 2 3 4 5
每次都会满足：
nums[mid] < nums[mid + 1]
所以 right 会不断往左收缩，最后停在 0，答案就是第一个元素。
情况 2：整个数组一直下降
比如：
5 4 3 2 1
每次都会满足：
nums[mid] > nums[mid + 1]
所以 left 会不断往右收缩，最后停在最后一个位置，答案就是最后一个元素。
8. 用样例模拟一遍
输入是：
9 7 5 3 4 6 8
一开始：
left = 0right = 6
第一次
mid = 3nums[mid] = 3nums[mid + 1] = 4
因为：
3 < 4
说明已经在上升段，所以最小值在 mid 或左边。
于是：
right = 3
第二次
left = 0right = 3mid = 1nums[mid] = 7nums[mid + 1] = 5
因为：
7 > 5
说明还在下降段，所以最小值在右边。
于是：
left = 2
第三次
left = 2right = 3mid = 2nums[mid] = 5nums[mid + 1] = 3
因为：
5 > 3
所以：
left = 3
现在：
left == right == 3
循环结束，答案就是：
nums[3] = 3
9. 总结
这题虽然表面上是在找“最小值”，但真正利用的不是“最小值”本身，而是这个数组的形状：先下降，再上升，所以一定存在一个谷底。而 binary search 做的事情就是：每次看一眼中间附近是在往下走还是往上走，然后决定谷底在哪一边，最后就能快速找到答案。