二分查找第一个大于或大于等于目标值的元素
哪些公司问过
答案要点
- 数组必须有序,无序时先排序 O(n log n),之后每次二分 O(log n)
- 左闭右开写法:right 初始为 n,a[mid]>=target 时 right=mid,否则 left=mid+1
- 循环结束 left 即第一个满足条件的位置,left==n 表示不存在
- “第一个大于”只需把条件改为 a[mid]>target,字符串用字典序比较
- “最后一个小于 x”等于“第一个大于等于 x”的下标减一,对应 lower_bound/upper_bound
易错点
- 区间定义和更新方式不一致,比如右开区间却写 right=mid-1,导致漏解或死循环
- 没处理不存在的情况,返回越界下标
- 在无序数组上直接二分
面试官常见追问
- 为什么 mid 用 left+(right-left)/2?
- 左闭右闭写法怎么写?
- 如何统计有序数组中某个数出现的次数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。