LeetCode-35-搜索插入位置

算法刷题>LeetCode>Hot100
2.5k words

问题描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路

这道题要求我们在排序数组中找到目标值的位置，如果目标值不存在，则返回它应该被插入的位置。由于题目要求算法时间复杂度为 O(log n)，很明显需要使用二分搜索。

对于此类问题，我们需要找到第一个大于等于目标值的元素索引，这正是二分搜索的一个常见应用场景，
但这一题容易模糊不清的就是对边界条件的处理。
要在数组中插入目标值，一共有四种情况：

  • 目标值在数组所有元素之前
  • 目标值是数组中的某一个元素
  • 目标值插入数组中的某一个位置
  • 目标值在数组所有元素之后

因此我们可以从暴力搜索和二分查找两个角度来解答该问题。

二分搜索基本原理

二分搜索的基本思想是将查找范围逐步缩小为原来的一半，直到找到目标元素或确定目标元素不存在。具体步骤如下(左闭右闭区间解法)：

  1. 设置左边界 left = 0 和右边界 right = n - 1
  2. 当 left <= right 时，计算中间位置 mid = left + (right - left) / 2
  3. 如果 nums[mid] == target，返回 mid
  4. 如果 nums[mid] < target，说明目标在右半部分，设置 left = mid + 1
  5. 如果 nums[mid] > target，说明目标在左半部分，设置 right = mid - 1
  6. 如果循环结束后仍未找到目标，那么 right + 1 就是目标值应该插入的位置

代码实现

暴力搜索

1
2
3
4
5
6
7
8
9
10
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;

这个方法非常简洁，时间复杂度为O(n),空间复杂度为O(1)，关键在于如何把前三种情况的判断条件写出来。

二分查找

闭区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution{
    public int searchInsert(int[]nums, int target){
        int n = nums.length;
        int left = 0, right = n - 1;
        int mid;
        while(left <= right){
            mid = left + ((right - left) >> 1);
            if(nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else 
                return mid;
        }
        return right + 1;
    }
}

二分查找结束条件是left > right，也就是说，无论有没有查询到，结束的时候，right一定在left的左边，此时，如果查询到了，则直接返回mid，没有查询到，则待插位置在right + 1。

左闭右开区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution{
    public int searchInsert(int[]nums, int target){
        int mid;
        int left = 0, right = nums.length;
        while(left < right){
            mid = left + ((right - left) >> 1);
            if(nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
            else 
                return mid;
        }
        return right;
    }
}

该写法除了right初始值，更新值需要改变之外，在最后return的时候，也是直接return right。
两种解法的最后return也可以统一写成return left，此时不需要考虑要不要加1的情况。left最终的位置一定是待插位置或者是待查位置。

注意事项和常见错误

使用二分搜索时，有几个常见的注意事项和潜在错误：

  1. 整数溢出：计算中间索引时，应使用 mid := left + (right-left)/2 而不是 mid := (left+right)/2，后者在大数据范围时可能导致整数溢出。

  2. 循环条件：根据需要选择 left <= right 或 left < right。前者在循环结束时有 left = right + 1，后者在循环结束时有 left = right。

  3. 边界更新：根据不同的搜索需求，边界更新方式也不同。例如，查找第一个满足条件的元素时，可能需要 right = mid，而不是 right = mid - 1。

复杂度分析

对于二分搜索：

  • 时间复杂度：$O(\log n)$，其中 $n$ 是数组的长度。每次操作都会将搜索范围缩小为原来的一半。
  • 空间复杂度：$O(1)$，只使用了常数额外空间。

总结

关键收获：

  1. 掌握 sort.Search 及其变体函数的用法和特性
  2. 了解五种常见的二分搜索变体及其适用场景
  3. 学会处理二分搜索中的边界条件和常见错误
  4. 掌握在实际编程中应用二分搜索的技巧

二分搜索不仅限于在数组中查找元素，还可以用于各种需要在有序空间中高效查找的场景，如二分答案、查找边界等。而且只要能找到一个判断条件把数组分割成两部分，我们都可以使用二分查找。灵活运用这种算法技术，将大大提高我们解决问题的效率。