二分查找

1. 一句话总结

二分的本质是在有单调性的答案空间里排除一半候选，不只是有序数组查找。

2. 通俗解释

二分像猜数字：每次问大了还是小了，只要答案能把范围分成两边，就能持续缩小区间。

3. 核心概念

• 基础二分：有序数组中查目标。
• 左边界：第一个满足条件的位置。
• 右边界：最后一个满足条件的位置。
• 二分答案：答案范围上找最小可行值或最大可行值。
• 单调性：条件随位置或答案单向变化。

4. 底层原理

• 二分每轮缩小一半，复杂度 O(log n)。
• 边界错误通常来自区间定义混乱。
• 找边界时命中也不能立刻返回，要继续收缩。
• mid 用 left + (right-left)//2 防止溢出。
• 二分答案要先写 check 函数判断可行性。

5. 面试标准回答

二分查找的核心不是数组有序，而是存在单调性，能根据中间位置判断答案在左边还是右边。普通二分用于找目标值，左右边界二分用于找第一个或最后一个满足条件的位置，二分答案在答案范围上找最小可行值或最大可行值。写代码时最重要的是统一区间定义，如闭区间或左闭右开，循环条件和更新方式要配套。找边界时命中后不能立即返回，而要继续缩小范围。

6. 高频追问

追问 1：二分查找面试第一句话怎么答？

先给结论：基础二分：有序数组中查目标。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

二分每轮缩小一半，复杂度 O(log n)。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：边界错误通常来自区间定义混乱。

追问 5：实际开发中怎么体现？

数据库索引查找利用有序结构快速定位。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 数据库索引查找利用有序结构快速定位。
• 容量规划类题可二分答案找最小资源。
• 日志时间戳有序时可二分快速定位范围。

9. 背诵速记

二分看单调性。每次用 mid 丢掉一半，复杂度 O(log n)。写法关键是区间定义统一。找边界时命中也继续收缩；二分答案先定范围，再写 check。