二分查找-35.搜索插入位置-力扣(LeetCode)

目录

一、题目解析

1.如果能在给定数组中找到目标值，则返回索引

2.如果目标值不存在，则返回将被插入的位置

3.必须使用时间复杂度为O(logN)的算法

二、算法解析

1.升序数组和时间复杂度O(logN)，二分查找

2.二段性

细节问题

对于示例3的情况需要判断nums[nums.size()-1]是否大于target，小于则返回nums.size()

三、代码示例

看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！

一、题目解析

1.如果能在给定数组中找到目标值，则返回索引

2.如果目标值不存在，则返回将被插入的位置

3.必须使用时间复杂度为O(logN)的算法

二、算法解析

1.升序数组和时间复杂度O(logN)，二分查找

2.二段性

细节问题

对于示例3的情况需要判断nums[nums.size()-1]是否大于target，小于则返回nums.size()

三、代码示例

class Solution {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        int left = 0,right = nums.size()-1;
        while(left<right)
        {   int mid = (left+right)/2;
            if(nums[mid]<target) left = mid + 1;
            else right = mid;
        }
        return target>nums[nums.size()-1] ? right+1 : right;
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！