[路飞]_leetcode-35-搜索插入位置

简介: leetcode-35-搜索插入位置

网络异常,图片无法展示
|


「这是我参与11月更文挑战的第4天,活动详情查看:2021最后一次更文挑战


[题目地址][B站地址]


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


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


示例 1:


输入: nums = [1,3,5,6], target = 5
输出: 2
复制代码


示例 2:


输入: nums = [1,3,5,6], target = 2
输出: 1
复制代码


示例 3:


输入: nums = [1,3,5,6], target = 7
输出: 4
复制代码


示例 4:


输入: nums = [1,3,5,6], target = 0
输出: 0
复制代码


示例 5:


输入: nums = [1], target = 0
输出: 0
复制代码


提示:


  • 1 <= nums.length <= 104
  • nums无重复元素升序排列数组
  • -104 <= target <= 104


本题就是让我们找到第一个大于等于目标值的位置即可。


针对这种问题,很自然的就想到可用使用 二分查找 来解题


二分查找


二分查找适用于在有序数组中找到第一个符合条件的位置


整体方法就是每次将搜索区间的中间值和目标值比较,通过大小关系判断目标值在当前区间的前半部分还是后半部分,然后将区间调整为对应部分,如此每次将查找区间减半,直到找到符合条件的元素或位置


至此,我们本题的解题思路就完成了,以下是代码实现


var searchInsert = function(nums, target) {
    if(target<nums[0]) return 0;
    if(target>nums[nums.length-1]) return nums.length;
    let l = 0,r = nums.length-1;
    while(l<r){
        const mid = (l+r)>>1;
        if(nums[mid]<target) l = mid+1
        else r = mid;
    }
    return l;
};
复制代码


至此,我们就完成了leetcode-35-搜索插入位置


如有任何问题或建议,欢迎留言讨论!

相关文章
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
15 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
20 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解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
46 4
|
4月前
|
算法 Python
【Leetcode刷题Python】74. 搜索二维矩阵
两种解决LeetCode "搜索二维矩阵" 问题的方法的Python实现。第一种方法是从二维矩阵的右上角开始线性搜索,通过比较当前元素与目标值来决定搜索方向。第二种方法是将二维矩阵视为一维数组进行二分查找,通过计算中间元素的行列索引来更新搜索区间。两种方法都旨在高效地判断目标值是否存在于给定的有序二维矩阵中。
43 0
|
4月前
|
算法 索引 Python
【Leetcode刷题Python】33. 搜索旋转排序数组
解决LeetCode "搜索旋转排序数组" 问题的Python实现代码。代码使用了二分查找算法,首先检查目标值是否存在于数组中,然后通过比较数组中间值与数组首尾值来确定应该在数组的哪一半继续搜索,直到找到目标值或搜索范围为空。如果找到目标值,返回其索引;如果搜索结束仍未找到,返回 -1。
19 0