ACM 选手图解 LeetCode 搜索插入位置

大家好呀，我是帅蛋。

今天解决搜索插入位置，同样作为二分查找的经典题。

这道题简单，但是不容易 AC，LeetCode 上的通过率很低，不足五成。

这就是之前我在【二分查找】文章里讲的，越简单的东西，越在细节上容易栽跟头。

废话不多说，下面就让我们来切了这道题。

   LeetCode 35：搜索插入位置

题意

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

如果目标值不在数组中，返回它将会被按顺序插入的位置。

示例

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

输出: 2

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

输出: 0

提示

必须使用时间复杂度为 O(logn) 的算法

• 1 <= len(nums) <= 10^4
  
• -10^4 <= nums[i]、target <= 10^4
  
• nums 为无重复元素的升序排列数组
  

题目解析

首先看题意，数组 nums 是无重复元素的升序排列数组，而且是必须使用 O(logn) 时间复杂度的算法。

说实话，当时看到这的时候我愣了一下，好家伙，直接报二分查找身份证号得了。

知道是二分查找，剩下就是走流程的事，但是这个和平常做的的二分查找还稍微有点不一样。

普通的二分查找的条件是：数组有序、无重复、能找到。

这里要二分查找的条件只是：数组有序、无重复，要找的 target 不一定在数组 nums 中。

target 在 nums 中没啥好说的，target 不在 nums 中，无非就存在 3 种情况：

• target < nums[0]，插在数组最前面
  
• target 插在某个数组元素后面
  
• target > nums[n-1]，插在数组最后面
  

基于这个情况，这道题的解题步骤如下：

• 初始化左右指针 low 和 high
  
• 每次计算中间指针 mid：若 num[mid] == target，直接返回 mid，若 nums[mid] < target，在右区间找，若 nums[mid] > target，在左区间找
  
• 查找结束，若没有相等的值，则返回 high + 1，此处为插入位置。
  

说一下最后一步“若没有相等的值，则返回 high + 1”：

对于二分查找，我的习惯查找的是［low, high］区间，区间是左闭右闭区间（当然你也可以是左闭右开区间）。

此时的 while 循环的条件是 low <= high，那循环终止条件相当于是 low = high + 1，此时区间是 [high + 1, high]。

循环终止代表 target 不在 nums 中，那它就要插入，插入的位置是 high 的右侧，即 high + 1（当然也可以是 left，毕竟此时 left 是等于 high + 1 的）。

如果还不理解的话找几个例子在纸上画一下，秒懂。

图解

以 nums = [1,3,5,6], target = 0 为例。

首先初始化 low 和 high 指针。

low, high = 0, len(nums) - 1

第 1 步，low = 0，high = 3，mid = (low + high) // 2 = 1：

mid = (low + high) // 2

此时 nums[mid] = 3 > target，所以 high 向左移动至 mid - 1 = 0 处。

if nums[mid] > target:
    high = mid - 1

第 2 步，low = 0，high = 0，mid = (low + high) // 2 = 0

此时 nums[mid] = 1 > target，所以 high 向左移动至 mid - 1 = -1 处。

第 3 步，low = 0，high = -1，此时 high < low，while 循环中止。

此时没有在数组中找到 target，证明 target 小于数组中最小的元素，所以插在下标为 -1 的位置，成为新的下标 0，即 high + 1。

本题解使用二分查找，时间复杂度为 O(logn)。

只额外定义了几个指针，空间复杂度为 O(1)。

代码实现

Python 代码实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        # 在 [low, high] 找 target
        while low <= high:
            mid = (low + high) // 2
            # 如果 target 找到，直接返回位置
            if nums[mid] == target:
                return mid
            # 如果 target 大于中间数，则 target 可能在右区间
            # 在 [mid + 1, left] 中找
            elif nums[mid] < target:
                low = mid + 1
            # 如果 target 小于中间数，则 target 可能在左区间
            # 在 [left, mid -1] 中找
            else:
                high = mid - 1
        # 如果在数组中没找到，则返回需要插入数值的位置
        return high + 1

Java 代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) { 
            int mid = low + (high - low) / 2; // 防止溢出
            if (nums[mid] > target) {
                high = mid - 1; 
            } else if (nums[mid] < target) {
                low = mid + 1; 
            } else {
                return mid;
            }
        }
        return high + 1;
    }
}

图解搜索插入位置到这就结束了。

还是要强调一下，二分查找本身是没难度的，但是二分查找是个细节控，稍不注意就容易出错。

大家在应用二分查找的时候还是要谨慎谨慎再谨慎。

有问题可以留言区留言，记得帮我点赞在看呀，么么哒。

我是帅蛋，我们下次见。