二分查找及其变体
哪些公司问过
答案要点
- 前提:数组有序;每次排除一半,时间 O(log n)
- 中点写成 lo + (hi - lo) / 2,避免溢出
- lower_bound:第一个 ≥ target;upper_bound:第一个 > target
- 第一个等于用 lower_bound 后检查;最后一个等于是 upper_bound - 1;次数 = upper - lower
- 旋转有序数组:先判断哪一半有序,再决定在哪半边查找
易错点
- 用 (lo + hi) / 2,导致整数溢出
- 区间定义和循环条件、更新方式不一致,造成死循环
- 有重复元素时没有处理边界
- 没有先判断数组是否有序或为空
面试官常见追问
- 循环条件写 lo < hi 还是 lo <= hi?
- 旋转有序数组怎么二分?
- 二分查找除了在数组里找值还能做什么?
- 数组有重复元素时,二分要注意什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。