【算法|二分查找No.3】leetcode 35. 搜索插入位置

太过爱你忘了你带给我的痛 2024-04-27 06:56 60阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣代码编写

## 1️⃣题目描述 ##

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

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

![在这里插入图片描述][c18e607bea544ab9b80484224ecac28a.png]

## 2️⃣代码编写 ##

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

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[Link 3]: https://leetcode.cn/problems/search-insert-position/description/
[c18e607bea544ab9b80484224ecac28a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/64badc9d04b4412ea3d5bd5038348718.png