LeetCode搜索插入位置
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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),其中 n 是数组的长度。所以可实现一个二分查找算法,用于在排序数组中查找一个目标值,并返回目标值的索引或者它应该被插入的位置。
代码
/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function(nums, target) {let left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right+1] >= targetconst mid = Math.floor((left + right) / 2);if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;
}
代码分析
-
初始化两个指针
left和right,分别指向数组的起始和结束位置,形成一个闭区间[left, right]。 -
进入一个
while循环,条件是left小于等于right,即区间不为空。 -
在循环内部,计算中间位置
mid,使用Math.floor((left + right) / 2)来确保mid是一个整数。 -
比较
nums[mid]和target的值:- 如果
nums[mid]小于target,则说明target可能在mid的右侧,因此更新left为mid + 1,这样新的搜索区间就变成了[mid + 1, right]。 - 如果
nums[mid]大于或等于target,则说明target可能在mid的左侧或mid本身,因此更新right为mid - 1,这样新的搜索区间就变成了[left, mid - 1]。
- 如果
-
当
while循环结束时,left指针将指向target应该被插入的位置。如果target在数组中存在,left将指向target的索引;如果target不存在,left将指向target应该被插入的位置,以保持数组的排序。 -
最后,函数返回
left作为结果。
这个算法的关键在于,每次迭代都会将搜索区间减半,这是通过比较中间元素和目标值来实现的。如果目标值在数组中,算法最终会找到它;如果目标值不在数组中,算法会找到目标值应该被插入的位置,以保持数组的排序。
这里可以自行走一遍示例,因为最后返回的是left,而判断最后是因为right减少导致循环结束,所以得到正确结果
相关文章:
LeetCode搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 …...
UE5学习笔记24-添加武器弹药
一、给角色的武器添加弹药 1.创建界面,根据笔记23的界面中添加 2.绑定界面控件 UPROPERTY(meta (Bindwidget))UTextBlock* WeaponAmmoAmount;UPROPERTY(meta (Bindwidget))UTextBlock* CarriedAmmoAmount; 3.添加武器类型枚举 3.1创建武器类型枚举头文件 3.2创建文…...
限制游客在wordpress某分类下阅读文章的数量
在WordPress中实现某个分类下的内容限制游客只能阅读前5篇文章,注册用户可以阅读更多文章的功能,可以通过以下步骤来完成: 1. 安装和激活插件 首先,你可以使用一个插件来简化这个过程。一个常用的插件是 “MemberPress” 或 “R…...
Oracle云主机申请和使用教程:从注册到SSH连接的全过程
今天我要和大家分享如何成功申请Oracle云主机,并进行基本的配置和使用。我知道很多同行的朋友在申请Oracle云主机时都遇到了困难(疑惑abc错误),可能试了很多次都没有成功。现总结一下这些年来的一些注册流程经验,或许你们也能成功申请到自己的…...
芯知识 | NVH-FLASH语音芯片支持平台做语音—打造音频IC技术革新
随着科技的飞速发展,人们对于电子产品的音频性能要求越来越高。在这种背景下,NVH-FLASH系列语音芯片应运而生,作为音频IC领域的一次重大技术革新,NVH-FLASH系列语音芯片凭借其卓越的性能与灵活的支持平台,正逐步引领着…...
机器学习——解释性AI与可解释性机器学习
解释性AI与可解释性机器学习: 理解机器学习模型背后的逻辑 随着人工智能技术的广泛应用,机器学习模型越来越多地被用于决策过程。然而,这些模型,尤其是深度学习模型,通常被视为“黑箱”,难以理解其背后的决策逻辑。解…...
中国全国省市区县汇总全国省市区json省市区数据2024最新
简介 包含全国省市区县数据,共3465个。 全国总共有23个省、5个自治区、4个直辖市、2个特别行政区。 ——更新于2024年10月16日,从2017年开始,已经更新坚持7年 从刚开始1000个左右的城市json,到现在全国省市区县3465个。 本人感觉应该是目前最完善的~ 每年都在更新中,…...
[Linux#67][IP] 报头详解 | 网络划分 | CIDR无类别 | DHCP动态分配 | NAT转发 | 路由器
目录 一. IP协议头格式 学习任何协议前的两个关键问题 IP 报头与有效载荷分离 分离方法 为什么需要16位总长度 如何交付 二. 网络通信 1.IP地址的划分理念 2. 子网管理 3.网络划分 CIDR(无类别域间路由) 目的IP & 当前路由器的子网掩码 …...
路由器原理和静态路由配置
一、路由器的工作原理 根据路由表转发数据 接收数据包→查看目的地址→与路由表进行匹配找到转发端口→转发到该端口 二、路由表的形成 它是路由器中维护的路由条目的集合,路由器根据路由表做路径选择,里面记录了网段ip地址和对应下一跳接口的接口号。…...
UE5 使用Animation Budget Allocator优化角色动画性能
Animation Budget Allocator是UE内置插件,通过锁定动画系统所占CPU的预算,在到达预算计算量时对动画进行限制与优化。 开启Animation Budget Allocator需要让蒙皮Mesh使用特定的组件,并进行一些编辑器设置即可开启。 1.开启Animation Budget…...
Element UI 组件库详解:从入门到精通
在追求统一且流畅的用户体验时,开发者们常常选择使用 UI 组件库来加快开发速度。Element UI,这个基于 Vue.js 的组件库,提供了大量界面组件,极大地提升了前端开发的效率。本文将指导您如何开始使用 Element UI 组件库,…...
JavaScript 事件循环(EventLoop) —— 浏览器 Node
一、事件循环的本质 本质:运行时对 JS 脚本的调度方式就叫做事件循环. 对于 浏览器 而言,需要考虑用户交互、UI渲染、脚本运行、网络请求等操作,这些操作必然都依赖于事件去执行,因此,为了协调事件必须要使用事件循环…...
【ROS2】订阅手柄数据,发布运动命令
1、相关消息 sensor_msgs::msg::Joy:用来描述手柄控制器数据 geometry_msgs::msg::Twist :用来描述物体运动时的线速度和角速度 参见博客: 【ROS2】geometry_msgs::msg::Twist和sensor_msgs::msg::Joy 2、订阅和发布 2.1 定义、创建订阅者和发布者 订阅手柄的按键、摇杆…...
WinX86内核02-驱动程序
把昨天的程序改用 c++ 编译,改成 .cpp ,发现编译报错 原因是名称粉碎,因此可以直接 extern “C”声明一下这个函数 或者用 头文件(推荐) 因为 在头文件中 可以把 头文件一起包含进去 #pragma once extern "C" { #include <Ntddk.h> /*驱动入口函…...
基于SpringBoot+Vue的体育馆场地预约系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
【WebGIS】Cesium:天地图加载
天地图是中国国家基础地理信息系统,由中国测绘地理信息局和国家地理信息公共服务平台共同开发和运营。它提供多项地理信息服务,包括地图数据、地理编码、路径规划以及地理搜索等。天地图的目标是为各行业提供高质量、全面的地理信息数据和解决方案。 天…...
[产品管理-46]:产品组合管理中的项目平衡与管道平衡的区别
目录 一、项目平衡 1.1 概述 1.2 项目的类型 1、根据创新程度和开发方式分类 2、根据产品开发和市场周期分类 3、根据风险程度分类 4、根据市场特征分类 5、根据产品生命周期分类 1.3 产品类型的其他分类 1、按物理形态分类 2、按功能或用途分类 3、按技术或创新程…...
【MySQL】MySQL的简单了解详解SQL分类数据库的操纵方法
一、mysql定义 mysql是数据库服务的客户端,mysqld是数据库服务的服务器端。mysql的本质就是基于CS模式下的一种网络服务。数据库一般指的是在磁盘中或内存中存储的特定结构组织的数据,将来就是在磁盘上存储的一套数据库方案。 创建数据库,本质…...
【Python爬虫实战】正则:从基础字符匹配到复杂文本处理的全面指南
🌈个人主页:https://blog.csdn.net/2401_86688088?typeblog 🔥 系列专栏:https://blog.csdn.net/2401_86688088/category_12797772.html 目录 前言 一、正则表达式 (一)正则表达式的基本作用 …...
10.18Python基础迭代器生成器_函数式编程
Python迭代器与生成器 1. 迭代器 Iterator 什么是迭代器 迭代器是访问集合元素的一种方式。迭代器是一个可以记住遍历的位置的对象。迭代器可以重复使用,而不会像列表那样在迭代时被修改。 迭代器函数iter和next 函数说明iter(iterable)从可迭代对象中返回一个迭…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
在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…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
