leetcode 35. 搜索插入位置(二分法+找性质也很关键)

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注 、点赞 、收藏🧡三连支持一下博主哦~~~

题目描述

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

请必须使用时间复杂度为 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

🧡 算法分析

此题方法是用二分

此题为简单的二分， 直接按照前面两题的思想做就行了

如果按照普通二分，那需要在边界情况加以判断

其实在这里是可以直接将l, r 的边界在开始设置时就扩大一点，在后面就不需要考虑当目标值比数组里的值都大得情况了
注意：这个利用模板不能通过得情况下，说明对于这题性质可能找错了，下面有利用不同性质进行对比

代码实现

普通二分+ 边界判断

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

        if (nums[l] < target) return l + 1;
        return l;
    }
};

开始就扩大范围int l = 0, r = nums.size();

1. 利用 if(nums[mid] <= target) l = mid; 通过不了， 需要写< . 然后在后面在加判断特殊情况

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        // 用这个模板不能通过，说明性质错了，边界点找错了
        int l = 0, r = nums.size();
        while(l < r)
        {
    
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;  
            else r = mid - 1;
        }
        return l ;
    }
};

2. 利用if(nums[mid] >= target) r = mid; 直接通过，不用外加特殊情况判断

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        int l = 0, r= nums.size();
        while(l < r )
        {
    
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

执行结果：

时间复杂度分析

时间复杂度为O(logn)

如果觉得对你有帮助的话:
点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
️ 评论，你的意见是我进步的财富！