【一周一算法】第五周：二分查找 · 思考题与练习详解

🧠 二分查找 · 思考题与练习详解

“二分查找的代码只有几行，但它包含的逻辑陷阱比几十行的代码还要多。”

🧩 思考题一：整型溢出的数学原理

❓ 问题

为什么 mid = low + (high - low) / 2 能够防止溢出？它和 (low + high) / 2 在数学上等价吗？

💡 详解

在数学上，两个公式是完全等价的：

$$L + \frac{H - L}{2} = \frac{2L}{2} + \frac{H - L}{2} = \frac{L + H}{2}$$

但在计算机的二进制世界里，情况不同：

假设 int 是 32 位有符号整数，最大值 INT_MAX 约为 21 亿。

1. 如果 low = 15亿，high = 15亿。
2. low + high = 30亿。这超过了 INT_MAX！ 此时发生上溢（Overflow），结果变成负数，导致程序崩溃。

而使用 low + (high - low) / 2：

1. high - low 一定是正数且小于 INT_MAX（前提是 low 和 high 都在合法范围内）。
2. high - low 除以 2 后更小，再加上 low，结果一定小于等于 high，绝对安全。

历史趣闻：这个 Bug 在 Java 的 Arrays.binarySearch 库中存在了 9 年才被发现并修复。

⚡ 思考题二：旋转排序数组的最小值

❓ 问题

如果一个有序数组在某个点旋转了（例如 [4,5,6,7,0,1,2]），如何用 $O(\log n)$ 找到最小值？（LeetCode #153）

💡 详解

这道题展示了二分查找**不再单纯依赖“大小”而是依赖“性质”**的经典应用。

性质分析：

旋转数组实际上被分成了两个单调递增的区间。最小值就是这两个区间的交界点。

二分策略：

我们拿 nums[mid] 和 右边界 nums[high] 进行比较：

1. 情况 A: nums[mid] > nums[high]
   • 例如 [4, 5, 6, 7, 0, 1, 2], mid=3 (val=7), high=6 (val=2)。
   • 7 > 2，说明 mid 还在左半段（大值区间）。最小值肯定在 mid 的右边。
   • low = mid + 1
2. 情况 B: nums[mid] < nums[high]
   • 例如 [7, 0, 1, 2], mid=2 (val=1), high=3 (val=2)。
   • 1 < 2，说明 mid 在右半段（小值区间）。mid 可能是最小值，也可能最小值在它左边。
   • high = mid (注意：不是 mid - 1，因为 mid 可能是答案)

代码实现：