LeetCode35 搜索插入位置:二分找下界
哪些公司问过
华为1微派网络1
答案要点
- 转化为找第一个大于等于 target 的位置,即 lower_bound
- 二分查找,时间 O(log n),空间 O(1)
- 左闭右开写法:right=n、left<right、right=mid,结束返回 left
- target 小于首元素返回 0、大于末元素返回 n,二分天然覆盖
- 区间定义与指针更新保持一致,mid 用 left+(right-left)/2 防溢出
易错点
- 开区间和闭区间的循环条件、更新方式混用导致死循环
- 找不到时返回 -1,而题目要求返回插入位置
- mid=(left+right)/2 在大下标时可能溢出
面试官常见追问
- 如果数组有重复元素,要返回 target 的第一个和最后一个位置怎么做?
- 什么情况下二分会死循环?
- C++ 标准库里有现成函数吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。