035.搜索插入位置
作者：沉默王二
发布时间：2024-06-15T11:00:33.595+0800
鲁迅曾说，人生就是一个曲折不断的过程，你可能正在向上求索，但成绩却不尽如人意。甚至这个时候还有人在背后捅你一刀，怎么办呢？这时候只能继续坚持，熬过去就对了。就像今天这道题，仍然是二分查找搜索插入位置，来吧，向前继续冲吧。
技术派阅读地址：https://paicoding.com/column/7/35
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 3 道大家完全都能掌握的题解（ 仍然是利用二分查找）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
题意
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
难度
简单
示例
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: 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 应该插入的位置。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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 用户。
分析 2
不过，题目仍然要求我们使用时间复杂度为 O(log n) 的算法，那就需要使用二分查找了。
试试 Arrays.binarySearch() 方法吧，如果找到了，直接返回索引，如果没找到，返回 -index - 1，这个值就是 target 应该插入的位置。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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() 的源码：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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 应该插入的位置。
来看一下题解效率，很不错。
分析 3
当然了，我们也可以手写二分查找法，不用 Arrays.binarySearch()。和之前 在排序数组中查找元素的第一个和最后一个位置 的写法差不多。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
mid = left + (right - left) / 2
= 0 + (3 - 0) / 2
= 1
比较 nums[mid] 和 target：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
nums[mid] = nums[1] = 3
由于 nums[1] < target，更新 left：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
left = mid + 1 = 1 + 1 = 2
第二次循环的时候，left = 2，right = 3，计算 mid：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
mid = left + (right - left) / 2
= 2 + (3 - 2) / 2
= 2
比较 nums[mid] 和 target：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
nums[mid] = nums[2] = 5
由于 nums[2] < target，更新 left：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
left = mid + 1 = 2 + 1 = 3
第三次循环的时候，left = 3，right = 3，计算 mid：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
mid = left + (right - left) / 2
= 3 + (3 - 3) / 2
= 3
比较 nums[mid] 和 target：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
nums[mid] = nums[3] = 6
由于 nums[3] < target，更新 left：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
left = mid + 1 = 3 + 1 = 4
此时 left = 4，right = 3，left > right，跳出循环，返回 left，即返回 4。
题解效率仍然不错。
总结
这道题仍然考察的是二分查找法，由此可见二分查找法的重要性。
去 B站搜了一下，这个 up 讲的不错，推荐大家看一下。
