当前位置: 首页 > article >正文

LeetCode:35. 搜索插入位置

🍎道阻且长,行则将至。🍓

🌻算法,不如说它是一种思考方式🍀


算法专栏: 👉🏻123


一、🌱35. 搜索插入位置

  • 题目描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
    请必须使用时间复杂度为 O(log n) 的算法
  • 来源:力扣(LeetCode)
  • 难度:简单
  • 提示:
    1 <= nums.length <= 104
    -104 <= nums[i] <= 104
    nums 为 无重复元素 的 升序 排列数组
    -104 <= target <= 104

🌴解题

这个题要求O(log n) 的算法,且就描述来看也是一个二分法的模子,也不用去考虑暴力搜索了。

二分法

不同的地方在于没有目标元素的时候要求返回一个插入的位置。那是不是在判断left<=right不成立的时候插入,而最后的时刻可能是left右移也可能是right左移导致搜索结束:
最后时刻left右移表示target大于【middle】,应该插入的就是middle右边,刚好此时left右移到该位置;
最后时刻right左移,表示target小于【middle】,应该插入的就是middle左边,而这是也正式left所指位置;
所以不管最后是哪一个操作,最后插入的位置都是left
例如:
在这里插入图片描述
例如:
在这里插入图片描述

  • code
        int middle ;
        int left=0,right= nums.length-1;
        while(left<=right){
            middle=left+(right-left)/2;
            if(target==nums[middle])
                return  middle;
            else if(target<nums[middle]){
                right=middle-1;
            }
            else{
                left=middle+1;
            }
        }

        return left;

在这里插入图片描述
本题只需要在搜索结束未命中的时候考虑在哪个位置插入。


☕物有本末,事有终始,知所先后。🍭

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓


http://www.kler.cn/a/2017.html

相关文章:

  • STM32F103 | Embedded IDE03 - 使用OpenOCD在STM32F103项目时出现下载固件失败
  • 【优选算法---归并排序衍生题目】剑指offer51---数组中的逆序对、计算右侧小于当前元素的个数、翻转对
  • 解决Apache/2.4.39 (Win64) PHP/7.2.18 Server at localhost Port 80问题
  • Go语言封装Cron定时任务
  • SAP HCM 考勤时间冲突到分 源码分析
  • 单调栈基础用法
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)
  • 100天精通Python(可视化篇)——第80天:matplotlib绘制不同种类炫酷柱状图代码实战(簇状、堆积、横向、百分比、3D柱状图)
  • python网上选课系统django-PyCharm
  • 新闻稿的写作格式
  • 【国产FPGA】国产FPGA搭建图像处理平台
  • 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.59】引入ASPP模块
  • RK3588平台开发系列讲解(NPU篇)RKNN SDK API流程
  • ChatGPT助力校招----面试问题分享(四)
  • Python Logging
  • Python爬虫——Python多线程爬虫详解
  • 血氧仪是如何得出血氧饱和度值的?
  • HTTPS协议,看这篇就够了
  • 二叉搜索树
  • 【canvas】简易小实例(钟表和画布)
  • 2023年全国最新道路运输从业人员精选真题及答案28
  • 【JavaEE】Thread 类及常用方法
  • 项目质量管理工作 不得不重视的4大关键点
  • web渗透之jwt 安全问题
  • 【Linux】Linux基本指令(下)
  • 让 new bing 使用 GPT-4 编写一个令人满意的程序全过程赏析