力扣HOT100（36）二分查找-搜索插入位置

题目核心要求给定一个无重复元素的升序数组和一个目标值如果目标值存在返回它的索引如果目标值不存在返回它按顺序应该插入的位置必须用 O (log n) 时间复杂度也就是只能用二分这道题的精髓就是把两个要求合并成一个问题求数组中第一个大于等于 target 的元素的下标为什么如果 target 存在第一个大于等于 target 的元素就是 target 本身返回它的索引如果 target 不存在第一个大于等于 target 的元素的位置就是 target 应该插入的位置如果 target 比所有数都大没有大于等于 target 的元素插入位置就是数组长度这一步转化是这道题的核心理解了这个代码就水到渠成了。和普通二分查找的区别普通二分找等于 target本题二分找第一个 target找到直接返回 mid找到不直接返回继续往左找更左边的没找到返回 - 1没找到返回插入位置不需要额外变量存结果需要 ans 变量存最终结果class Solution { public: int searchInsert(vectorint nums, int target) { int n nums.size(); int left 0,right n-1,ans n;//如果target比所有的数都大 那么直接返回ans n; while(left right){//当左小于等于右的时候 int mid ((right - left)/2) left;//不写成right left /2的形式 是因为避免left和right太大 导致栈溢出 if(target nums[mid]){ ans mid;//缩小区域如果下面还是都比target小 那么就返回mid right mid - 1;//缩短到0到mid-1 } else{ left mid 1 ;//如果target比中间值大 那么就把左边界右移 } } return ans; } };先留好最坏情况的退路把ans初始化为数组长度n提前处理「target 比所有数都大插在最后」的情况不断缩小搜索范围如果target nums[mid]说明mid是一个可能的插入位置先记下来然后往左缩看看有没有更靠前的位置如果target nums[mid]说明mid左边肯定插不了往右缩去右边找循环结束答案自然出来当区间空了left rightans里存的就是第一个大于等于 target 的位置也就是最终的插入位置