二分搜索看似简单，但有很多微妙的变体是面试官喜欢考的。边界错误是最常见的bug。此题考察你是否真正理解不变量，能否将二分搜索应用于非显而易见的问题。
从标准二分搜索开始：有序数组，O(log n) 时间，O(1) 空间。
讲下界（第一次出现）和上界（最后一次出现）变体。
解释旋转有序数组的二分搜索——非常热门的面试题。
介绍答案空间上的二分搜索：不能直接搜索数组时，对可能的答案值进行二分。
标准二分搜索在有序数组中通过反复将搜索空间减半，O(log n) 找到目标。关键变体有：下界找值第一次出现或可插入的位置——找到目标后继续向左搜索。上界找最后位置——继续向右搜索。旋转有序数组如 [4,5,6,7,0,1,2]，我通过比较 mid 和 left 判断哪半边有序，再检查目标是否落在有序半边。答案空间二分搜索用于优化问题：如求 d 天内运送包裹的最小载重，对载重值二分，贪心检查可行性。二分搜索的关键是定义清晰的循环不变量：每次迭代中 left 和 right 代表什么。我总是用 left < right 模式，根据 mid 是否可能是答案来决定 right = mid 还是 right = mid - 1。
编码前明确定义不变量：left 和 right 分别代表什么？
使用 mid = left + (right - left) / 2 避免整数溢出。
用大小为 0、1、2 的数组测试你的解法，捕捉边界错误。
为 left 和 right 定义清晰的不变量。提前决定搜索范围是 [left, right] 还是 [left, right)，坚持一种约定，用小数组测试。
不搜索数组，而是对可能的答案值二分。对每个候选值检查可行性。适用于"最小化最大值"或"最大化最小值"类优化问题。
不能直接用，但可用于任何具有单调性的搜索空间——如果能定义一个从 false 变为 true 的条件，就能二分搜索边界。