一、题目描述给定一个升序、无重复元素的排序数组和一个目标值target。需求如果数组中存在target返回对应索引如果不存在返回target按升序插入的位置强制要求时间复杂度O(log n)。示例nums [1,3,5,6], target 5→ 输出2找到元素nums [1,3,5,6], target 2→ 输出1插入到 3 前面nums [1,3,5,6], target 7→ 输出4插入到末尾题目核心限制必须二分不能遍历。遍历是O(n)会不满足题目要求。二、解题思路为什么是二分查找二分查找的适用条件数组有序本题升序时间复杂度要求O(log n)这道题不只是简单的“找数”而是找数 / 找插入位置一体的二分模板题是二分最经典的入门题型。核心结论背诵级重点在left right的二分模板中成功找到target直接返回mid循环结束、未找到targetleft就是最终插入位置原理循环结束时一定满足left right此时left指向第一个大于target的元素下标恰好是target应该插入的位置。三、完整 C AC 代码LeetCode 可直接提交#includevectorusingnamespacestd;classSolution{public:intsearchInsert(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){// 规避整数溢出优于 (left right) / 2intmidleft(right-left)/2;if(nums[mid]target){// 找到目标值直接返回下标returnmid;}elseif(nums[mid]target){// 目标在右区间左边界右移leftmid1;}else{// 目标在左区间右边界左移rightmid-1;}}// 未找到left 为插入位置returnleft;}};四、逐流程图解推演以nums [1,3,5,6], target 2为例初始left 0, right 3mid 1nums[1] 3 2→right 0mid 0nums[0] 1 2→left 1此时left(1) right(0)循环结束返回left 1正确插入位置以target 7为例全部元素都比 7 小循环结束后left最终走到数组末尾下标 4完美对应末尾插入的情况。五、高频易错点新手必看mid 写法溢出问题错误写法mid (left right) / 2数据量大时会 int 溢出。正确写法mid left (right - left) / 2等价且安全。循环条件写错必须是left right如果写成left right会漏掉边界元素插入位置计算错误。循环结束返回 right很多新手这里翻车一定返回left不是right。循环结束left指向插入位right指向插入位的前一位。提交多余代码报错LeetCode 只需要Solution类 函数不需要main、cout、iostream带上会编译报错。六、复杂度分析时间复杂度O(log n)每次循环将区间缩小一半严格满足题目要求空间复杂度O(1)仅使用常数变量无额外空间开销七、模板总结通用二分查找插入模板适用于有序无重复数组、查找元素 / 查找插入位置场景可直接套用到同类题目while(leftright){intmidleft(right-left)/2;if(nums[mid]target)returnmid;elseif(nums[mid]target)leftmid1;elserightmid-1;}returnleft;八、刷题感悟这道题是二分查找的地基题看似简单却包含了二分最核心的边界逻辑。很多人学不会二分就是因为搞不懂「循环结束后left、right的含义」。吃透这道题的边界逻辑后续所有二分查找、二分答案题目都能轻松上手。
