二分查找的原理、复杂度与边界处理
哪些公司问过
答案要点
- 前提是序列有序且支持随机访问,每轮比较中点后丢弃一半区间
- 时间复杂度 O(log n),迭代实现空间 O(1)
- 区间定义要和循环条件、边界更新一致,如左闭右闭配 left<=right 和 mid±1
- mid 用 left+(right-left)/2 计算,防止 left+right 溢出
- 有重复元素时用 lower_bound/upper_bound 变体找第一个或最后一个位置
易错点
- 区间开闭和循环条件不一致,导致死循环或漏掉元素
- mid 直接写 (left+right)/2,大下标时整数溢出
- 对无序数据或链表直接套二分
面试官常见追问
- 有重复元素时如何找第一个等于 target 的位置?
- 旋转过的有序数组还能二分吗?
- 除了查找元素,二分还能用在哪?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。