当前位置: 首页 > 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:…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...