[LeetCode] 35.搜索插入位置(Easy)Java语言题解

1.题目相关

①题目及示例

Alt text

②相关标签

  • 数组
  • 二分查找

③题目地址


2.解题方法

①顺序查找

  • 根据题意可以看出,数组中第一个大于或等于 target 的元素对应的下标就是 target 将要插入的位置,若是数组中的元素都比 target 小,则返回数组长度。
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

②二分查找

  • 结论:
    • 每次判断 nums[mid] 和 target 之间的大小:
    • 若 nums[mid] = target,则直接返回下标。
    • 若 nums[mid] < target,则 left = mid + 1。
    • 若 nums[mid] > target,则 right = mid - 1。
    • 查找结束后返回 left,该值为插入位置。
  • 这道题的难点是如果数组中不包含值和 target 相等的元素,那么我们要返回什么呢?上文的结论是返回 left,那么我们是如何得到的呢?
  • 此时我们可以想象程序在最后一次循环中会做什么:
    • 已知程序结束循环的条件是 left > right,所以我们可以确定在最后一次循环中有:right == left -> mid == (right + left) / 2 == right == left,此时存在两种情况:
1
2
3
4
5
if (nums[mid] < target) {
// left > right,之后退出循环。
left = mid + 1;
}
// 退出循环后,nums[left] = nums[right + 1] > target。
1
2
3
4
5
if (nums[mid] > target) {
// right < left,之后退出循环。
right = mid - 1;
}
// 退出循环后,nums[left] = nums[mid] > target。
  • 根据上述证明可知,返回 left 是正确的。
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

注意:修改以上代码的返回结果,也可以用于求解其他题目。

  1. 返回 left,表示查找比 target 大的最小数的位置,适用于本题以及 278. 第一个错误的版本744. 寻找比目标字母大的最小字母 等题。
  2. 返回 right,表示查找比 target 小的最大数的位置,适用于 441. 排列硬币69. x 的平方根 等题。
  3. 返回 -1 或者 false,表示查找不到 target,适用于 704. 二分查找367. 有效的完全平方数74. 搜索二维矩阵 等题。
  4. 如果题目中说明一定能找到 target,这时返回哪个值都可以,适用于 852. 山脉数组的峰顶索引 等题。

3.代码详解

①暴力解法

1
2
3
4
5
6
7
8
9
public int searchInsert(int[] nums, int target) {
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] >= target) {
return i;
}
}
return len;
}

②二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
// int mid = (left + right) / 2;
// int mid = left + (right - left) / 2;
int mid = (left + right) >>> 1;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left;
}

附录

0%