LeetCode 35. 搜索插入位置（二分查找）

客官°小女子只卖身不卖艺 2022-11-29 13:09 129阅读 0赞

**上一篇博客：[LeetCode 28. 实现 strStr()（KMP、字符串）][LeetCode 28. _ strStr_KMP]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 35. 搜索插入位置][LeetCode 35.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
     *   *  示例 1
         *  示例 2
         *  示例 3
         *  示例 4
 *  题解
 *   *  解题思路
     *  解题代码
     *  时间复杂度
     *  提交结果
 *  二分查找模板
 *   *  模板1
     *  模板2

# 题目信息 #

## 题目描述 ##

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

你可以假设数组中无重复元素。

## 示例 ##

### 示例 1 ###

> 输入: \[1,3,5,6\], 5  
> 输出: 2

### 示例 2 ###

> 输入: \[1,3,5,6\], 2  
> 输出: 1

### 示例 3 ###

> 输入: \[1,3,5,6\], 7  
> 输出: 4

### 示例 4 ###

> 输入: \[1,3,5,6\], 0  
> 输出: 0

# 题解 #

## 解题思路 ##

我们可以使用 `二分查找算法` 来解决这个问题。我们不断的进行二分查找直到找到目标值 `target` ，找不到则返回第一个大于等于 `target` 的值的下标。因为题目给定的是一个排序数组，所以我们在开始的时候可以特判一下目标值 `target` 是否比数组最后一个数大，如果比最后一个数都大的话，我们直接返回数组的长度即可。即目标值 `target` 应该插入到数组的最后一个位置。  
![图解1][1]  
![图解2][2]

## 解题代码 ##

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

## 时间复杂度 ##

假设 **n** 为数组的长度。二分查找所需的时间复杂度为 **O(logn)**。

## 提交结果 ##

![提交结果][20200821165003744.png]

# 二分查找模板 #

二分查找有两个模板，区别在于当 `r = mid - 1` 的时候我们每次求 **mid** 的时候要 `+1`，这样可以防止我们的二分查找出现死循环的情况。

## 模板1 ##

当我们将区间 `[l, r]` 划分成 `[l, mid]` 和 `[mid + 1, r]` 时，其更新操作是 `r = mid` 或者 `l = mid + 1;`，**计算 mid 时不需要加 1**。

int Search_Bin(int l, int r) { 
    	
        while (l < r) { 
        	int mid = l + r >> 1;
        	if (check(mid)) r = mid;
        	else l = mid + 1;
        }
        
        return l;
    }

## 模板2 ##

当我们将区间 `[l, r]` 划分成 `[l, mid - 1]` 和 `[mid, r]` 时，其更新操作是 `r = mid - 1` 或者 `l = mid`，此时为了防止死循环，计算 mid 时需要加 1。

int Search_Bin(int l, int r) { 
    	
        while (l < r) { 
        	int mid = l + r + 1 >> 1;
        	if (check(mid)) l = mid;
        	else r = mid - 1;
        }
        
        return l;
    }

--------------------

> 未完待续，持续更新中……  
> ![今天谁也别想阻止我好好学习][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

[LeetCode 28. _ strStr_KMP]: https://ac-fun.blog.csdn.net/article/details/108140789
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 35.]: https://leetcode-cn.com/problems/search-insert-position/
[1]: /images/20221124/908fdbfa01cf4923b7207f62ead6f7c2.png
[2]: /images/20221124/1be917f45dfc406db1cbfde6b7c41eb0.png
[20200821165003744.png]: /images/20221124/56335a52654641fb93efd67976df7806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221124/77b47904f1f941ada1bd66ad2e04686c.png