35. 搜索插入位置

鲁迅曾说，人生就是一个曲折不断的过程，你可能正在向上求索，但成绩却不尽

如人意。甚至这个时候还有人在背后捅你一刀，怎么办呢？这时候只能继续坚

持，熬过去就对了。就像今天这道题，仍然是二分查找搜索插入位置，来吧，向

前继续冲吧。

题意

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存

在于数组中，返回它将会被按顺序插入的位置。

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

难度

简单

示例

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

输出: 2

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

输出: 1

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

输出: 4

分析 1

同样，在不考虑时间复杂度的情况下，我们来看一下这道题的解法。

①、如果目标值在数组中，那就是直接遍历数组，找到和 target 相等的元素，返回索引即

可。

②、如果目标值不在数组中，题目要求返回插入的位置，那么由于数组是排序过的（默认

都是正序），那么第一个大于 target 的元素位置，就是 target 应该插入的位置。

class Solution {

public int searchInsert(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

if (nums[i] >= target) {

return i;

}

}

return nums.length;

}

}

直接一个 for 循环 + 一个 if 判断，就搞定了，并且仍然能击败 100% 的 Java 用户。

035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE-20

240615095159.png

分析 2

不过，题目仍然要求我们使用时间复杂度为 O(log n) 的算法，那就需要使用二分查找了。

试试 Arrays.binarySearch() 方法吧，如果找到了，直接返回索引，如果没找到，返回

-index - 1，这个值就是 target 应该插入的位置。

class Solution {

public int searchInsert(int[] nums, int target) {

int index = Arrays.binarySearch(nums, target);

return index >= 0 ? index : -index - 1;

}

}

为什么 -index - 1 就是 target 应该插入的位置呢？

来看一下 Arrays.binarySearch() 的源码：

public static int binarySearch(int[] a, int key) {

return binarySearch0(a, 0, a.length, key);

}

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {

int low = fromIndex;

int high = toIndex - 1;

while (low <= high) {

int mid = (low + high) >>> 1;

int midVal = a[mid];

if (midVal < key)

low = mid + 1;

else if (midVal > key)

high = mid - 1;

else

return mid; // key found

}

return -(low + 1); // key not found.

}

如果找到了，直接返回索引，这没啥好说的。如果没找到，也就是当 while 循环结束时，

说明数组中没有目标值。

return -(low + 1)：返回一个负数，表示目标值不在数组中。这种返回值的含义如下：

• low 是在数组中第一个大于目标值的位置。

• -(low + 1) 会返回一个负数，这样可以通过检查返回值是否为负数来判断目标值是否

存在于数组中。

• 之所以返回 -(low + 1) 而不是 -low，是因为如果 low 的值是 0，直接返回 -low 会得

到 0，这与找到的索引 0 混淆。通过返回 -(low + 1)，总是返回一个负数，这样可以

明确区分查找成功和查找失败。

那既然应该返回 0 的时候返回了-1，那么通过 -(-(low + 1)) - 1 也就是 low，就是 target

应该插入的位置。

来看一下题解效率，很不错。

035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE-20

240615103502.png

分析 3

当然了，我们也可以手写二分查找法，不用 Arrays.binarySearch()。和之前 在排序数组

中查找元素的第一个和最后一个位置 的写法差不多。

class Solution {

public int searchInsert(int[] nums, int target) {

int left = 0;

int right = nums.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid] < target) {

left = mid + 1;

} else if (nums[mid] > target) {

right = mid - 1;

} else {

return mid;

}

}

return left;

}

}

我们来模拟一下当输入 nums = [1, 3, 5, 6] 和 target = 7 时，代码的执行过程。

第一次循环的时候，left = 0，right = 3，计算 mid：

mid = left + (right - left) / 2

= 0 + (3 - 0) / 2

=1

比较 nums[mid] 和 target：

nums[mid] = nums[1] = 3

由于 nums[1] < target，更新 left：

left = mid + 1 = 1 + 1 = 2

第二次循环的时候，left = 2，right = 3，计算 mid：

mid = left + (right - left) / 2

= 2 + (3 - 2) / 2

=2

比较 nums[mid] 和 target：

nums[mid] = nums[2] = 5

由于 nums[2] < target，更新 left：

left = mid + 1 = 2 + 1 = 3

第三次循环的时候，left = 3，right = 3，计算 mid：

mid = left + (right - left) / 2

= 3 + (3 - 3) / 2

=3

比较 nums[mid] 和 target：

nums[mid] = nums[3] = 6

由于 nums[3] < target，更新 left：

left = mid + 1 = 3 + 1 = 4

此时 left = 4，right = 3，left > right，跳出循环，返回 left，即返回 4。

题解效率仍然不错。

035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE-20

240615104704.png

总结

这道题仍然考察的是二分查找法，由此可见二分查找法的重要性。

去 B 站搜了一下，这个 up 讲的不错，推荐大家看一下。

数据结构合集 - 折半查找(二分查找)

035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE-20

240615105143.png

力扣地址：https://leetcode.cn/problems/search-insert-position/