35-搜索插入位置(Search Insert Position)

原文链接: https://leetcode-cn.com/problems/search-insert-position

英文原文

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

中文题目

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

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

示例 4:

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

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

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

通过代码

高赞题解

这篇题解分成「本题题解」「二分查找重点概括」和「二分查找题型练习」三个部分。

关键：写对「二分查找」的重点，从来不在于二分查找怎么写，而在于分析题意，根据题目的条件和要求思考如何缩减区间。

在学习「二分查找」以及其它算法和数据结构的过程中，我们可能会有各种各样的疑问，把它们记录下来，思考得多了，很多问题自然就有答案。

本题题解

在有序数组中查找，可以使用「二分查找」。

分析：

根据示例，分析题目要我们返回的「插入元素的位置」到底是什么。根据示例 3：

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

如果目标元素大于输入数组中的最后一个元素，题目需要我们返回数组的最后一个元素的下标 + 1。又根据示例 2：

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

因此题目需要我们返回第 1 个 大于等于（等于的情况可以看示例 1）目标元素 2 的下标，因此返回 1。因此 如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是题目要求的结果，根据这一点可以写出本题二分查找算法的完整逻辑。

参考代码 1：

[]
public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        // 特殊判断
        if (nums[len - 1] < target) {
            return len;
        }

        // 程序走到这里一定有 nums[len - 1] >= target
        int left = 0;
        int right = len - 1;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

说明：由于执行到最后 nums[left..right] 里一定存在插入元素的位置，退出循环的时候一定有 left == right 成立，因此返回 left 或者 right 都可以。

复杂度分析：

时间复杂度：$O(\log N)$，这里 $N$ 是输入数组的长度；
空间复杂度：$O(1)$。

既然 len 也有可能是答案，可以在初始化的时候，把 right 设置成 len，此时就不需要特殊判断了。

参考代码 2：

[]
public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

复杂度分析：（同参考代码 1）

二分查找重点概括

写成 while(left < right) ，退出循环的时候有 left == right 成立，好处是不用判断应该返回 left 还是 right；
区间 [left..right] 划分只有以下两种情况：
- 分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1；
- 分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要将 int mid = (left + right) / 2 改成 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了；
退出循环 left == right，如果可以确定区间 [left..right] 一定有解，直接返回 left 就可以。否则还需要对 left 这个位置单独做一次判断；
二分查找的循环不变量是：在区间 [left..right] 里查找目标元素。

关于如何写对二分查找，二分查找的详细讲解，可以查看我编写的 LeetBook 的「二分查找」章节。

二分查找题型练习

提示：这些问题都不应该当做模板问题来看待。下面是这些问题的题解，重点分析了应该如何思考，讲解了如何编写正确的代码，希望能够对大家有所帮助。

题型一：二分下标（在数组中查找符合条件的元素的下标）

一般而言这个数组是有序的，也可能是半有序的（旋转有序数组或者山脉数组）。

题目	题解	说明
704. 二分查找（简单）		二分查找的最原始问题，使用本题解介绍的方法就要注意，需要后处理。
34. 在排序数组中查找元素的第一个和最后一个位置（中等）	文字题解、视频题解	查找边界问题。
33. 搜索旋转排序数组（中等）	文字题解	利用局部单调性，逐步缩小搜索区间（其它问题类似）。
81. 搜索旋转排序数组 II（中等）	文字题解
153. 寻找旋转排序数组中的最小值（中等）	文字题解
154. 寻找旋转排序数组中的最小值 II（中等）	文字题解
300. 最长上升子序列（中等）	文字题解。	特别经典的一道「动态规划」，二分查找的思路基于「动态规划」的状态定义得到，代码很像第 35 题。
275. H指数 II（中等）	文字题解	这个问题题目的描述让人迷惑，可以跳过不做。
852. 山脉数组的峰顶索引（简单）		利用局部单调性，逐步缩小搜索区间。
1095. 山脉数组中查找目标值（中等）	文字题解、视频题解
4. 寻找两个有序数组的中位数（困难）	文字题解、视频题解
658. 找到 K 个最接近的元素（中等）	文字题解	这个问题二分的写法需要做复杂的分类讨论，可以放在以后做。

题型二：二分答案（在一个有范围的区间里搜索一个整数）

定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。

事实上，二分答案是我们最早接触的二分查找的场景。「幸运 52」里猜价格游戏，就是「二分查找」算法的典型应用：先随便猜一个数，如果猜中，游戏结束。如果猜大了，往小猜；如果猜小了，往大猜。

题目	题解	说明
69. 平方根（简单）	文字题解	在一个整数范围里查找一个整数，也是二分查找法的应用场景。
287. 寻找重复数（中等）	文字题解	在一个整数范围里查找一个整数。这个问题二分查找的解法很反常规（不应该用时间换空间，这么做太傻了），知道即可。
374. 猜数字大小（简单）	文字题解
1300. 转变数组后最接近目标值的数组和	文字题解

题型三：二分答案的升级版：判别条件需要遍历数组

说明：这里给出的问题解法都一样，会一题等于会其它题。问题的场景会告诉我们：目标变量和另一个变量有相关关系（一般是线性关系），目标变量的性质不好推测，但是另一个变量的性质相对容易推测（满足某种意义上的单调性）。这样的问题的判别函数通常会写成一个函数的形式。

这一类问题可以统称为「 最大值极小化 」问题，最原始的问题场景是木棍切割问题，这道题的原始问题是「力扣」第 410 题（分割数组的最大值（困难））。

思路是这样的：

分析出题目要我们找一个整数，这个整数有范围，所以可以用二分查找；
分析出 单调性，一般来说是一个变量 a 的值大了，另一个变量 b 的值就变小，而「另一个变量的值」 b 有限制，因此可以通过调整 a 的值达到控制 b 的效果；
这一类问题的题目条件一定会给出连续、正整数 这样的关键字。如果没有，问题场景也一定蕴含了这两个关键信息。

以下给出的问题无一例外。

题目	提示与题解	说明
410. 分割数组的最大值（困难）	文字题解
875. 爱吃香蕉的珂珂（中等）	文字题解
LCP 12. 小张刷题计划（中等）		题解在第 410 题题解里
1482. 制作 m 束花所需的最少天数（中等）		题解在第 1300 题题解里
1552. 两球之间的磁力（中等）

统计信息

通过次数	提交次数	AC比率
576650	1252818	46.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
第一个错误的版本	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途