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

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

大家好呀,我是帅蛋。


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


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


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


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

640.png


   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) 时间复杂度的算法。


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

640.jpg


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


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


这里要二分查找的条件只是:数组有序、无重复,要找的 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 的)。


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

640.jpg


图解


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


首先初始化 low 和 high 指针。

640.png

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


第 1 步,low = 0,high = 3,mid = (low + high) // 2 = 1:

640.png

mid = (low + high) // 2

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

640.png


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

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

640.png


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

640.png

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


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

640.jpg


本题解使用二分查找,时间复杂度为 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;
    }
}


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


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


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


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


我是帅蛋,我们下次见。


相关文章
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
15 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
16 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
4月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
4月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
4月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
4月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
43 4
|
4月前
|
算法 Python
【Leetcode刷题Python】74. 搜索二维矩阵
两种解决LeetCode "搜索二维矩阵" 问题的方法的Python实现。第一种方法是从二维矩阵的右上角开始线性搜索,通过比较当前元素与目标值来决定搜索方向。第二种方法是将二维矩阵视为一维数组进行二分查找,通过计算中间元素的行列索引来更新搜索区间。两种方法都旨在高效地判断目标值是否存在于给定的有序二维矩阵中。
41 0
|
4月前
|
算法 索引 Python
【Leetcode刷题Python】33. 搜索旋转排序数组
解决LeetCode "搜索旋转排序数组" 问题的Python实现代码。代码使用了二分查找算法,首先检查目标值是否存在于数组中,然后通过比较数组中间值与数组首尾值来确定应该在数组的哪一半继续搜索,直到找到目标值或搜索范围为空。如果找到目标值,返回其索引;如果搜索结束仍未找到,返回 -1。
19 0