搜索插入位置

这篇具有很好参考价值的文章主要介绍了搜索插入位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

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

请必须使用时间复杂度为 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

算法思想:

由于该题指定算法时间复杂度 为O(log n),则该题的解题思路可以利用二分法来进行求解。
另外,二分法,一定要注意区间范围,否则容易出现边界错误。文章来源地址https://www.toymoban.com/news/detail-647643.html

代码生成:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left= 0,right = nums.size()-1,middle;
        while(left <= right)
        {
            middle = (left + right)/2;
            if(nums[middle] < target)
                left = middle + 1;
            else if(nums[middle] > target)
                right = middle - 1;
            else  return middle;
        }
        return left;
    }
};

到了这里,关于搜索插入位置的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】700、LeetCode二叉搜索树中的搜索

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :二叉搜索树(Binary Search Tree, BST)的性质:所有左子树节点键值 中间节点键值 所有右子树节点键值,并且左右子树都是二叉搜索树。那么我们根据此性质,对比目标值和中间节点,如

    2024年02月10日
    浏览(41)
  • 【算法与数据结构】98、LeetCode验证二叉搜索树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :注意不要落入下面你的陷阱,笔者本来想左节点键值中间节点键值右节点键值即可,写出如下代码:   在leetcode执行时遇到下面的错误,再次读题,发现是所有左子树的键值小于

    2024年02月09日
    浏览(38)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(61)
  • java数据结构与算法刷题-----LeetCode96. 不同的二叉搜索树

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只

    2024年01月21日
    浏览(56)
  • 数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)

    验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/ 描述 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身

    2024年02月16日
    浏览(40)
  • 【算法刷题day22】Leetcode:235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 50.删除二叉搜索树中的节点

    文档链接:[代码随想录] 题目链接:235. 二叉搜索树的最近公共祖先 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年04月13日
    浏览(40)
  • 【Leetcode每日一题】35.搜素插入位置|二分查找数组下标

    🌱博主简介:大一计科生,努力学习Java中!热爱写博客~预备程序媛 📜所属专栏:LeetCode每日一题–进击大厂 ✈往期博文回顾: 【JavaSE】保姆级教程|1万字+10张图学会类与对象–建议收藏 🕵️‍♂️近期目标:成为千粉小博主。 🌺“再牛的程序员也是从小白开始,既然开始

    2024年02月21日
    浏览(65)
  • 【算法Hot100系列】搜索插入位置

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月03日
    浏览(45)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(68)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包