有序数组中统计 k 的出现次数
哪些公司问过
答案要点
- 有序数组中 k 是连续的一段,找左右边界即可
- 二分找第一个 ≥ k 和第一个 > k 的位置,相减得次数
- k 不存在时两位置相同,结果为 0
- 时间 O(log n);C++ 可用 upper_bound 减 lower_bound
- mid 用 left + (right - left) / 2 防溢出,统一区间写法
易错点
- 找到一个 k 后向两边线性扩展,最坏退化成 O(n)
- 左右边界的二分条件写混,导致差 1
面试官常见追问
- 如果数组是降序的呢?
- 如果数组旋转过,还能二分统计吗?
- 二分查找左边界的模板怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。