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

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;
}

代码分析

  1. 初始化两个指针 leftright,分别指向数组的起始和结束位置,形成一个闭区间 [left, right]

  2. 进入一个 while 循环,条件是 left 小于等于 right,即区间不为空。

  3. 在循环内部,计算中间位置 mid,使用 Math.floor((left + right) / 2) 来确保 mid 是一个整数。

  4. 比较 nums[mid]target 的值:

    • 如果 nums[mid] 小于 target,则说明 target 可能在 mid 的右侧,因此更新 leftmid + 1,这样新的搜索区间就变成了 [mid + 1, right]
    • 如果 nums[mid] 大于或等于 target,则说明 target 可能在 mid 的左侧或 mid 本身,因此更新 rightmid - 1,这样新的搜索区间就变成了 [left, mid - 1]
  5. while 循环结束时,left 指针将指向 target 应该被插入的位置。如果 target 在数组中存在,left 将指向 target 的索引;如果 target 不存在,left 将指向 target 应该被插入的位置,以保持数组的排序。

  6. 最后,函数返回 left 作为结果。

这个算法的关键在于,每次迭代都会将搜索区间减半,这是通过比较中间元素和目标值来实现的。如果目标值在数组中,算法最终会找到它;如果目标值不在数组中,算法会找到目标值应该被插入的位置,以保持数组的排序。

这里可以自行走一遍示例,因为最后返回的是left,而判断最后是因为right减少导致循环结束,所以得到正确结果

相关文章:

LeetCode搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 …...

UE5学习笔记24-添加武器弹药

一、给角色的武器添加弹药 1.创建界面&#xff0c;根据笔记23的界面中添加 2.绑定界面控件 UPROPERTY(meta (Bindwidget))UTextBlock* WeaponAmmoAmount;UPROPERTY(meta (Bindwidget))UTextBlock* CarriedAmmoAmount; 3.添加武器类型枚举 3.1创建武器类型枚举头文件 3.2创建文…...

限制游客在wordpress某分类下阅读文章的数量

在WordPress中实现某个分类下的内容限制游客只能阅读前5篇文章&#xff0c;注册用户可以阅读更多文章的功能&#xff0c;可以通过以下步骤来完成&#xff1a; 1. 安装和激活插件 首先&#xff0c;你可以使用一个插件来简化这个过程。一个常用的插件是 “MemberPress” 或 “R…...

Oracle云主机申请和使用教程:从注册到SSH连接的全过程

今天我要和大家分享如何成功申请Oracle云主机,并进行基本的配置和使用。我知道很多同行的朋友在申请Oracle云主机时都遇到了困难&#xff08;疑惑abc错误&#xff09;,可能试了很多次都没有成功。现总结一下这些年来的一些注册流程经验&#xff0c;或许你们也能成功申请到自己的…...

芯知识 | NVH-FLASH语音芯片支持平台做语音—打造音频IC技术革新

随着科技的飞速发展&#xff0c;人们对于电子产品的音频性能要求越来越高。在这种背景下&#xff0c;NVH-FLASH系列语音芯片应运而生&#xff0c;作为音频IC领域的一次重大技术革新&#xff0c;NVH-FLASH系列语音芯片凭借其卓越的性能与灵活的支持平台&#xff0c;正逐步引领着…...

机器学习——解释性AI与可解释性机器学习

解释性AI与可解释性机器学习: 理解机器学习模型背后的逻辑 随着人工智能技术的广泛应用&#xff0c;机器学习模型越来越多地被用于决策过程。然而&#xff0c;这些模型&#xff0c;尤其是深度学习模型&#xff0c;通常被视为“黑箱”&#xff0c;难以理解其背后的决策逻辑。解…...

中国全国省市区县汇总全国省市区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&#xff08;无类别域间路由&#xff09; 目的IP & 当前路由器的子网掩码 …...

路由器原理和静态路由配置

一、路由器的工作原理 根据路由表转发数据 接收数据包→查看目的地址→与路由表进行匹配找到转发端口→转发到该端口 二、路由表的形成 它是路由器中维护的路由条目的集合&#xff0c;路由器根据路由表做路径选择&#xff0c;里面记录了网段ip地址和对应下一跳接口的接口号。…...

UE5 使用Animation Budget Allocator优化角色动画性能

Animation Budget Allocator是UE内置插件&#xff0c;通过锁定动画系统所占CPU的预算&#xff0c;在到达预算计算量时对动画进行限制与优化。 开启Animation Budget Allocator需要让蒙皮Mesh使用特定的组件&#xff0c;并进行一些编辑器设置即可开启。 1.开启Animation Budget…...

Element UI 组件库详解:从入门到精通

在追求统一且流畅的用户体验时&#xff0c;开发者们常常选择使用 UI 组件库来加快开发速度。Element UI&#xff0c;这个基于 Vue.js 的组件库&#xff0c;提供了大量界面组件&#xff0c;极大地提升了前端开发的效率。本文将指导您如何开始使用 Element UI 组件库&#xff0c;…...

JavaScript 事件循环(EventLoop) —— 浏览器 Node

一、事件循环的本质 本质&#xff1a;运行时对 JS 脚本的调度方式就叫做事件循环. 对于 浏览器 而言&#xff0c;需要考虑用户交互、UI渲染、脚本运行、网络请求等操作&#xff0c;这些操作必然都依赖于事件去执行&#xff0c;因此&#xff0c;为了协调事件必须要使用事件循环…...

【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的体育馆场地预约系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

【WebGIS】Cesium:天地图加载

天地图是中国国家基础地理信息系统&#xff0c;由中国测绘地理信息局和国家地理信息公共服务平台共同开发和运营。它提供多项地理信息服务&#xff0c;包括地图数据、地理编码、路径规划以及地理搜索等。天地图的目标是为各行业提供高质量、全面的地理信息数据和解决方案。 天…...

[产品管理-46]:产品组合管理中的项目平衡与管道平衡的区别

目录 一、项目平衡 1.1 概述 1.2 项目的类型 1、根据创新程度和开发方式分类 2、根据产品开发和市场周期分类 3、根据风险程度分类 4、根据市场特征分类 5、根据产品生命周期分类 1.3 产品类型的其他分类 1、按物理形态分类 2、按功能或用途分类 3、按技术或创新程…...

【MySQL】MySQL的简单了解详解SQL分类数据库的操纵方法

一、mysql定义 mysql是数据库服务的客户端&#xff0c;mysqld是数据库服务的服务器端。mysql的本质就是基于CS模式下的一种网络服务。数据库一般指的是在磁盘中或内存中存储的特定结构组织的数据&#xff0c;将来就是在磁盘上存储的一套数据库方案。 创建数据库&#xff0c;本质…...

【Python爬虫实战】正则:从基础字符匹配到复杂文本处理的全面指南

&#x1f308;个人主页&#xff1a;https://blog.csdn.net/2401_86688088?typeblog &#x1f525; 系列专栏&#xff1a;https://blog.csdn.net/2401_86688088/category_12797772.html 目录 前言 一、正则表达式 &#xff08;一&#xff09;正则表达式的基本作用 &#xf…...

10.18Python基础迭代器生成器_函数式编程

Python迭代器与生成器 1. 迭代器 Iterator 什么是迭代器 迭代器是访问集合元素的一种方式。迭代器是一个可以记住遍历的位置的对象。迭代器可以重复使用&#xff0c;而不会像列表那样在迭代时被修改。 迭代器函数iter和next 函数说明iter(iterable)从可迭代对象中返回一个迭…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...