二分查找算法(4) _搜索插入位置

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

二分查找算法(4) _搜索插入位置

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

温馨提示:

1. 题目链接:

2. 题目描述 :

3. 解法(二分查找) :

    算法思路 :

    代码展示 :

    结果分析 :

4. 二分算法模板总结

温馨提示:

这道题是直接使用了二分模板,轻松拿捏了这道题,如果你还不知道的话,自行去下篇博客

---二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板-CSDN博客

1. 题目链接:

OJ链接:搜索插入位置

2. 题目描述 :

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

注意:请必须使用时间复杂度为 O(log n) 的算法。

3. 解法(二分查找) :

    算法思路 :

因为这道题对时间复杂度有要求,所以这里就不写暴力算法,直接使用二分查找

由于题目中的数组是有序数组,我们可以利用数组的二段性,将数组分成两部分:

        1. 数组中的数 <= target

        2. 数组中的数 > target

这样我们就可以使用二分算法进行查找,直接套用我们之前已经讲解过的二分算法

    代码展示 :

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

    结果分析 :

这里我们的算法时间复杂度为: log(N)满足题目要求.

4. 二分算法模板总结

这里再次强调一下我们的二分算法模板(真的很好用!!!)

while(left < right)
 
{
 
        int mid = left + (right - left) / 2;
 
        if(...) left = mid + 1;
 
        else right = mid;
}
 
while(left < right)
 
{
 
        int mid = left + (right - left + 1) / 2;
 
        if(...) left = mid;
 
        else right = mid - 1;
}

快速记忆:

分类讨论的代码,就题论题即可

下面出现-1,上面就+1,否侧不加