LeetCode(搜索插入位置)

简介: 如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。

搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0,right = nums.size() - 1;
        int mid;
        while(left < right)
        {
            mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        //没有找到的情况 left == right
        return target <= nums[left] ? left : right+1;
    }
};

直接使用二分查找法降低时间复杂度为O(log n) ,然后再二分查找的基础上修改一下,当left == right的情况来处理数组中没有目标数据的情况,但是仅仅是做了一个下标处理,并没有将数据真正插入到数组之中,因为题目仅仅是要返回目标数据应该被插入的位置

下标处理考虑三种情况
1.数据插入到数组头部
如果数据最小,那么循环结束的left == right == 0,因此直接返回left
2.数据插入到数组尾部
如果数据最大,那么循环结束的left == right == nums.size() - 1,因此返回left+1或者right+1即可
3.数据插入到数组中部
target > 最终的nums[left]则返回left+1或者right+1
target < 最终的nums[left]则返回left或者right即可
target = nums[left]的情况: 数组中只有一个元素[1] target = 1,直接返回left即可

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