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

力扣算法题:35、搜索插入位置.java版

版本说明

当前版本号[20230928]。

版本修改说明
20230928初版

35.搜索插入位置

点击此处跳转到力扣页面

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

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

提示:

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

思路

可以点击此篇博客看二分查找算法相关的图解:究竟是什么样的讲解二分查找算法的博客让我写了三小时???

​ 这道题目是一个经典的二分查找问题,要求在一个排序数组中找到目标值的索引,如果目标值不存在,则返回它将被按顺序插入的位置。

解题思路如下:

  1. 首先,定义两个指针 i 和 j,分别指向数组的首部和尾部。

  2. 通过 while 循环,不断缩小搜索的范围,直到 i 大于 j

  3. 在循环中,计算中间位置 m = (i + j) >>> 1(无符号右移一位,等价于除以2)。

  4. 如果目标值小于等于中间值 nums[m],则说明目标值可能在左半部分,将 j 更新为 m - 1

  5. 如果目标值大于中间值 nums[m],则说明目标值可能在右半部分,将 i 更新为 m + 1

  6. 重复上述步骤,直到找到目标值或者搜索范围缩小到 i 大于 j(找到目标值)

  7. 返回 i 的值,即为目标值的索引或者插入位置。

    ​ 该算法的时间复杂度为 O(log n),因为每次都将搜索范围缩小为原来的一半,直到找到目标值或搜索范围为空。

代码

基础版

基础版代码具体的工作流程如下:

  1. 首先,定义两个指针 ij,分别指向数组的首部和尾部。
  2. 通过 while 循环,在满足 i <= j 的条件下进行查找。
  3. 在循环中,计算中间位置 m,使用无符号右移一位 (i + j) >>> 1 来避免溢出。
  4. 如果目标值 target 小于当前中间值 a[m],则说明目标值可能在左半部分,将 j 更新为 m - 1
  5. 如果中间值 a[m] 小于目标值 target,则说明目标值可能在右半部分,将 i 更新为 m + 1
  6. 如果中间值 a[m] 等于目标值 target,则说明找到了目标值,直接返回索引 m
  7. 重复上述步骤,直到找到目标值或搜索范围缩小到 i > j
  8. 最后,如果找到了目标值,则返回对应的索引;如果没有找到,则返回插入位置 i

注:原始代码中返回的是 -1,但实际应该是返回插入位置 i

public int searchInsert(int[] a, int target) {int i = 0, j = a.length - 1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else if (a[m] < target) {i = m + 1;} else {return m;}}return i; // 原始 return -1
}

优化版

​ 普通版与优化版这两段代码实际上是相同的,只是变量名不同。

​ 优化之处在于代码的可读性和简洁性,通过使用有意义的变量名和清晰的逻辑结构,使得代码更易于理解。返回值即为插入位置,并能处理元素重复的情况。

​ 将 target < a[m]target = a[m] 的情况优化在一起target <= nums[m] ,并少了一层的判断,这样的优化并不会改变算法的时间复杂度和核心思想,但可以提高代码的可读性和可维护性。

​ 都是使用二分查找在给定的排序数组中找到目标值的索引,如果目标值不存在,则返回它将被按顺序插入的位置。

class Solution {public int searchInsert(int[] nums, int target) {int i = 0;int j = nums.length - 1;while (i <= j){int m = (i + j) >>> 1;if(target <= nums[m]){j = m -1 ;}else{i = m + 1 ;}}return i;}
}

总结

​ 这道题目是要求在给定的排序数组中,使用二分查找的算法找到目标值的索引,如果目标值不存在,则返回它将被插入的位置。

总结一下解题思路和步骤:

  1. 定义两个指针 ij,分别指向数组的首部和尾部。

  2. 使用 while 循环,在满足 i <= j 的条件下进行查找。

  3. 在循环中,通过计算中间位置 m 来获取中间元素的索引,使用无符号右移一位 (i + j) >>> 1 来避免溢出。

  4. 如果目标值 target 小于当前中间值 a[m],则更新 j = m - 1,因为目标值可能在左半部分。

  5. 如果中间值 a[m] 小于目标值 target,则更新 i = m + 1,因为目标值可能在右半部分。

  6. 如果中间值 a[m] 等于目标值 target,则说明找到了目标值,直接返回索引 m

  7. 重复上述步骤,直到找到目标值或者搜索范围缩小到 i > j

  8. 最后,如果找到了目标值,则返回其索引;如果没有找到,则返回插入位置 i

    ​ 这种二分查找算法的时间复杂度为 O(log n),其中 n 是数组的长度。通过在每一次比较中将搜索范围缩小一半,可以高效地找到目标值或插入位置。

    ​ 在编码实现时,需要注意边界条件、循环终止条件和变量更新的逻辑。通过理解并正确实现这个二分查找算法,可以在排序数组中快速地找到目标值的索引或插入位置。

相关文章:

力扣算法题:35、搜索插入位置.java版

版本说明 当前版本号[20230928]。 版本修改说明20230928初版 35.搜索插入位置 点击此处跳转到力扣页面 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必…...

七、热力图展示

在开发3d模型之中&#xff0c;热力图是非常常见的需求&#xff0c;比如需要了解人口密度&#xff0c;空气质量&#xff0c;热力分布等这些都需要热力图来展示&#xff0c;那么3d常见的热力图是怎么实现的呢&#xff0c;现在我们就来看看。先看效果图。 思路&#xff1a; 1引入h…...

基于微信小程序的新闻发布平台小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

【论文阅读】Directional Connectivity-based Segmentation of Medical Images

目录 摘要介绍方法效果结论 论文&#xff1a;Directional Connectivity-based Segmentation of Medical Images 代码&#xff1a;https://github.com/zyun-y/dconnnet 摘要 出发点&#xff1a;生物标志分割中的解剖学一致性对许多医学图像分析任务至关重要。 之前工作的问题&…...

借“牛油果”爆款出圈,甜啦啦的底牌只是“价格”?

上架10日&#xff0c;累计销量超过500万杯。近日&#xff0c;甜啦啦新品“超牛牛油果”瞬间成为门店新晋“爆款”。势头正劲的甜啦啦乘胜追击&#xff0c;袒露了自己的新目标&#xff0c;计划2025年进军北美、欧洲等地区&#xff0c;并在同年开启上市征途。 甜啦啦袒露的新目标…...

【C语言】快速排序

文章目录 一、hoare版本二、挖坑法三、前后指针法四、非递归快排五、快速排序优化1、三数取中选key值2、小区间优化 六、代码测试 一、hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&#xff1a;任取待排序元素序列中的某元素…...

Java列表查询Long(id)到前端转换出错

Java列表查询Long到前端转换出错 问题描述排查思路思路一&#xff1a;SQL问题思路二&#xff1a;Long类型转换出错 解决方法 问题描述 做了一个列表查询功能&#xff0c;本来不应该有啥大问题的&#xff0c;但是往往事与愿违。 诶&#xff0c;你越觉得不可能出问题&#xff0c…...

react import爆红

如上所示&#xff0c;会标红&#xff0c; 解决办法&#xff1a;在vscode内部SHiftCtrlP 输入Reload window, 如上的第一个&#xff0c;选中后回车&#xff0c;标红就没了&#xff0c;非常好用。...

ThreeJS-3D教学三:平移缩放+物体沿轨迹运动

我们在项目中会有一些这样的需求&#xff0c;我们可视化一个场景&#xff0c;需要俯视、平移、缩放&#xff0c;方便观察场景中的数据或者模型&#xff0c;之所以把这个案例拿出来 1、这是个很实用的需求&#xff0c;我相信很多人会用到 2、我自己认为在实际案例中我们可以学习…...

玩玩“小藤”开发者套件 Atlas 200I DK A2 之VSCode远程连接

玩玩“小藤”开发者套件 Atlas 200I DK A2 之VSCode远程连接 0. 背景1. VSCode 安装 Remote - SSH 插件2. 安装 OpenSSH 组件3. VSCode SSH 连接 Atlas 200I DK A24. 打开远程文件夹 0. 背景 总所周知&#xff0c;英伟达的GPU供不应求&#xff0c;还各种限制。华为推出了升腾A…...

安装python中tensorflow和keras==2.2.0的路程

1.python中安装Keras2.3.0 你可以使用pip来安装特定版本的Keras。在命令行中运行以下命令&#xff1a; pip install keras2.3.0这将会下载并安装Keras的2.3.0版本及其相应的依赖项。请确保你的Python环境已经配置好&#xff0c;并且有足够的权限来安装软件包。2.python 中安装…...

Linux命令历史记录管理:使用history命令提高工作效率

文章目录 引言1.1 关于history命令1.2 history命令的作用和用途 基本用法2.1 查看历史命令列表2.2 执行历史命令2.3 使用历史命令编号 历史命令记录和保存3.1 历史命令的存储位置3.2 修改历史命令记录数量3.3 清除历史命令记录 搜索历史命令4.1 使用关键字搜索4.2 按日期和时间…...

Armv9 Cortex-A720的L1 memory system 和 L1 Cache

思考: L1 System memory和L1 Cache是什么关系?L1指令cache禁用时,指令cache就真的不会缓存了吗?此时还会出现缓存不一致的情况吗?L1 data cache禁用时,L1 data cache就真的不会缓存了吗?此时还会出现缓存不一致的情况吗?在下电的时候,cache有什么自动的行为?有没有in…...

使用超声波清洗机洗眼镜有哪些注意事项、高颜值超声波清洗机推荐

眼镜&#xff0c;对于许多人来说&#xff0c;不仅仅是矫正视力的工具&#xff0c;更是日常生活的重要伴侣。但是&#xff0c;眼镜的清洁问题却常常让人感到困扰。镜片上的污渍、指纹、甚至小划痕&#xff0c;都让眼镜的使用体验大打折扣。幸运的是&#xff0c;随着科技的进步&a…...

23种设计模式汇总详解

设计原则 中文名称英文名称含义解释单一职责原则Single Responsibility Principle(SRP)任何一个软件模块都应该只对某一类行为者负责一个类只干一件事&#xff0c;实现类要单一开闭原则Open-Close Principle(OCP)软件实体&#xff08;类、模块、函数等&#xff09;应该是可以扩…...

stream流的filter和map过滤

详情页面 // 过滤出身高大于 170 的记录 personList.stream().filter((item)->item.getHeight() > 170).forEach(System.out::println);//从对象中提取age。并过滤年龄 List<Integer> nameListstudentList.stream().map(StudentInfo::getAge).filter(f->f>…...

Linux 环境下使用 Docker 部署 Seata 1.7.1 (图文教程)

目录 前言环境准备创建数据库安装 Seata下载镜像自定义配置文件自定义配置启动 Seata 开源项目微服务商城项目 前后端分离项目联系我 前言 本篇参考 Seata 官方部署文档 在 Linux 环境通过 Docker 部署 Seata 1.7.1 版本&#xff0c;以及为 youlai-mall 开源商城版本的升级做…...

Aruba CX交换机 VSF配置

目前 Aruba CX 交换机中的 6300F 和 6300M 支持 VSF 功能&#xff0c;要求同型号堆叠。 6300 交换机仅仅最后 4 个 SFP56 端口支持 VSF link 6200F : all uplink ports with 10G speed can be configured as VSF link 6200F: VSF allows stacks to be formed using any combin…...

使用ElementUI结合Vue完善主页的导航菜单和书籍管理以及后台数据分页查询

目录 动态树 数据表 案列 书籍管理 动态树 动态树&#xff08;Dynamic tree&#xff09;是一种数据结构&#xff0c;它可以在树中动态地插入、删除和修改节点。与静态树不同&#xff0c;静态树的节点是固定的&#xff0c;一旦构建完成就无法再进行修改。而动态树可以在运行时…...

子序列问题集合

子序列问题 删除一次得到的最大和最大子数组和最长公共子序列&#xff1a;最长上升子序列&#xff08;要输出序列&#xff0c;和最大长度&#xff09;1.dp2.贪心二分 导弹拦截 &#xff08;最长上升/下降子序列长度&#xff09; 删除一次得到的最大和 class Solution { public:…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...