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

【面试经典 150 | 二分查找】搜索插入位置

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:二分查找
      • 闭区间
      • 左闭右开区间
      • 开区间
      • 总结
  • 知识总结
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【二分查找】【数组】


题目来源

35. 搜索插入位置


题目解读

其实就是找出数组中大于等于 target 的最小值所在的位置。


解题思路

在数组中找到第一个大于或者等于 target 值的所在位置,数据量不大,约为 O ( 1 0 4 ) O(10^4) O(104),可以一次遍历查找,也开始使用二分查找来解决。题目要求使用时间复杂度为 O ( l o g n ) O(logn) O(logn) 的算法,那就只能使用二分法来解答了。

方法一:二分查找

二分查找是一种高效的搜索算法,在有序数组的指定区间内根据要求搜索元素,根据当前区间的中点的搜索情况缩短区间,每次搜索都会缩短一半的区间,时间复杂度为 O ( l o g n ) O(logn) O(logn) n n n 为有序数组的长度。

二分查找根据区间的开闭分为以下三种情况:

  • 闭区间;
  • 左闭右开区间;
  • 开区间。

二分查找的区间无论是哪种闭合形式,要关注的 问题 始终是三个:

  • 一是何时退出循环;
  • 二是表示左、右区间的左、右指针如何移动;
  • 三是返回什么。

以下将针对三种二分法的三个问题分别进行分析。

闭区间

闭区间表示搜索的区间是闭合的,初始的闭合区间为 [0, n-1],即指针指向 l = 0, r = n-1

何时退出循环?

当区间为空的时候退出 while 循环,何时区间为空?

l > r 时,指针 l 位于指针 r 右侧已经构不成区间了,退出 while 循环。

因此,此时的 while 循环条件为 l <= r

左、右指针如何移动?

在闭区间情况下,如果 nums[mid] < target,说明 >= target 的值在右侧区间,于是只需要更新左指针 l = mid + 1;否则(nums[mid] >= target)说明 mid 及其之后的位置都是确定大于 target 的,这时候需要更新右指针 r = mid - 1 来判断左区间内的数。

返回什么?

退出循环后,r 指向的位置为 l 指向位置左侧的第一个位置,最后返回 l 或者 r + 1

实现代码

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1;while (l <= r) {        // 区间为空退出循环int mid = l + ((r - l) >> 1);if (nums[mid] < target) {l = mid + 1;}else {r = mid - 1;}}return l; // 等价于 return r+1}
};

左闭右开区间

左闭右开区间表示搜索的区间是左闭右开的,初始的指针指向为 l = 0, r = n

何时退出循环?

当区间为空的时候退出 while,何时区间为空?

因为 r 指针是取不到的,所以当 l = r 时,区间为空(因为实际的区间左端点为 l,右端点为 r,构不成区间),退出 while 循环。

此时的 while 循环条件为 l < r

左、右指针如何移动?

在左闭右开区间情况下,如果 nums[mid] < target,说明 >= target 的值在右侧区间,于是只需要更新左指针 l = mid + 1;否则(nums[mid] >= target)说明 mid 及其之后的位置都是确定大于 target 的,这时候需要更新右指针 r = mid 来判断左区间即 [l, mid-1] 中的数。

返回什么?

退出循环后,rl 指向的是同一个位置,最后返回 l 或者 r

实现代码

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n;while (l < r) {        // 区间为空退出循环int mid = l + ((r - l) >> 1);if (nums[mid] < target) {l = mid + 1;}else {r = mid;}}return l; // 等价于 return r}
};

开区间

开区间表示搜索的区间两边都是开的,初始的指针指向为 l = -1, r = n

何时退出循环?

当区间为空的时候退出 while,何时区间为空?

因为 lr 指针指向的值是取不到的,所以当 l + 1 = r 时,(l, r) 表示的区间为空,退出 while 循环。

此时的 while 循环条件为 l + 1 < r

左、右指针如何移动?

在开区间情况下,如果 nums[mid] < target,说明 >= target 的值在右侧区间,于是只需要更新左指针 l = mid(因为左区间是开的,实际的区间是 mid + 1);否则(nums[mid] >= target)说明 mid 及其之后的位置都是确定大于 target 的,这时候需要更新右指针 r = mid 来判断左区间即 [l, mid - 1] 中的数。

返回什么?

退出循环后,l 指向的位置位于 r 指向位置的左侧,最后返回 r 或者 l+1

总结

无论是哪种区间闭合形式,关注的始终是:何时退出while循环、左右指针如何更新以及最后返回什么这三个问题。

需要注意的移动指针一定要保证原来区间的闭合与否:原来区间是闭合的,更新后的指针指向的依旧是闭合的区间;原来区间是开的,更新后的指针指向的依旧是开的区间。

以上三种形式,可以挑选一种自己熟悉的形式记忆,并记住这是解决在有序数组中查找大于等于指定值的代码。


知识总结

在有序数组中查找大于等于指定值的最小位置的二分查找方法是十分经典,该方法已经被封装成了一个函数 lower_bound(),该方法之所以是经典是因为其他类型的查找都可以通过它来完成:

  • 在有序数组中查找大于等于指定值的最小位置,这就不赘述了;
  • 在有序数组中查找大于指定值 x 的最小位置,本题及以下等价转换仅限于整数数组。此时可以等价转化为 “在有序数组中查找大于等于指定值 x+1 的最小位置”;
  • 在有序数组中查找小于指定值 x 的最大位置,可以等价转化为 “在有序数组中查找大于等于指定值 x 的最小位置” 减 1
  • 在有序数组中查找小于等于指定值 x 的最大位置,可以等价转化为 “在有序数组中查找大于等于指定值 x+1 的最小位置” 减 1

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

相关文章:

【面试经典 150 | 二分查找】搜索插入位置

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;二分查找闭区间左闭右开区间开区间总结 知识总结写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c…...

DAPP开发【06】nodejs安装与npm路径更换

windows系统在执行用户命令时顺序 windows系统在执行用户命令时&#xff0c;若用户未给出文件的绝对路径&#xff0c; 则 &#xff08;1&#xff09;首先在当前目录下寻找相应的可执行文件、批处理文件等&#xff1b; &#xff08;2&#xff09;若找不到&#xff0c;再依次在系…...

数据结构奇妙旅程之顺序表和链表

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …...

vitepress的使用

创建项目并启动项目 // 1.创建项目,直接在空项目下安装vitepress(npm/yarn等都可以,这个可以看官网,官网给了好几种安装方式) yarn add -D vitepress // 2.初始化配置项目(npm/官网也给了多种包管理工具的安装方式) npx vitepress init // 初始化命令执行完会遇到以下几个问题…...

Discuz论坛自动采集发布软件

随着网络时代的不断发展&#xff0c;Discuz论坛作为一个具有广泛用户基础的开源论坛系统&#xff0c;其采集全网文章的技术也日益受到关注。在这篇文章中&#xff0c;我们将专心分享通过输入关键词实现Discuz论坛的全网文章采集&#xff0c;同时探讨采集过程中伪原创的发布方法…...

B树在数据库的应用

B树&#xff08;B-tree&#xff09;是一种自平衡的树状数据结构&#xff0c;广泛应用于数据库和文件系统等领域&#xff0c;其设计的目标是提供一种高效的插入、删除和查找操作。B树的设计是为了在磁盘等存储介质上存储和操作大量的数据。 主要特点包括&#xff1a; 平衡性&a…...

Android 源码编译

一&#xff0c;虚拟机安装 ​ 1.1 进入https://cn.ubuntu.com/download中文官网下载iso镜像 1.2 这里我们下载Ubuntu 18.04 LTS 1.3虚拟VM机安装ubuntu系统&#xff0c;注意编译源码需要至少16G运行内存和400G磁盘空间&#xff0c;尽量设大点 二 配置编译环境 2.1 下载andr…...

信而泰 SSL测试方法介绍

[本文介绍在ALPS平台上进行SSL测试的内容和方法] 什么是SSL SSL全称是Secure Sockets Layer&#xff0c;指安全套接字协议&#xff0c;为基于TCP的应用层协议提供安全连接&#xff1b;SSL介于TCP/IP协议栈的第四层和第五层之间&#xff0c;广泛用于电子商务、网上银行等。 SSL…...

Redis--15--缓存穿透 击穿 雪崩

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 缓存穿透 击穿 雪崩运行速度:1 缓存穿透问题描述:如何解决: 2 缓存击穿问题描述:如何解决: 3 缓存雪崩说明:解决方案: 缓存穿透 击穿 雪崩 问题描述: 由于海量的用…...

excel表格在线编辑(开源版)

文章目录 前言一、Luckysheetvue3vite 例子如有启发&#xff0c;可点赞收藏哟~ 前言 本文记录好用的开源在线表格 具体如图显示 另外记录下更名后的univer~&#xff0c;如下图&#xff08;有兴趣可自行详细了解&#xff09; univer 在线思维导图 一、Luckysheet 参考git…...

17.字符串处理函数——字符串比较函数

文章目录 前言一、题目描述 二、解题 程序运行代码 总结 前言 本系列为字符串处理函数编程题&#xff0c;点滴成长&#xff0c;一起逆袭。 一、题目描述 二、解题 程序运行代码 #include<stdio.h> #include<string.h> int main() {char *str1 "hello wo…...

【面试HOT200】二叉树——深度优先搜索篇

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于【CodeTopHot200】进行的&#xff0c;每个知识点的修正和深入主要参…...

价值投资选股的方法

价值投资法是一种长期投资策略&#xff0c;其核心思想是寻找被市场低估的股票&#xff0c;即股票的市场价格低于其内在价值。这种策略认为&#xff0c;投资者应该关注公司的基本面&#xff0c;如盈利能力、成长潜力、财务状况等&#xff0c;而不是短期的市场波动。以下是价值投…...

java中如何将mysql里面的数据取出来然后通过stream流的方式进行数据处理代码实例?

在 Java 中使用 Stream 流的方式从 MySQL 数据库中取出数据并进行处理&#xff0c;你可以通过 JDBC&#xff08;Java Database Connectivity&#xff09;来实现。下面是一个简单的代码示例&#xff1a; import java.sql.*; import java.util.stream.Stream; public class MySQ…...

C++服务器 支持http、tcp protobuf、websocket,linux开源框架 零依赖轻松编译部署 Reactor

开源地址: https://github.com/crust-hub/tubekit/tree/main Github:https://github.com/gaowanlu 诚招有兴趣的小伙伴加入开发维护 Tubekit The C TCP server framework based on the Reactor model continues to implement POSIX thread pool, Epoll, non blocking IO, obj…...

1688API接口系列,1688开放平台接口使用方案(商品详情数据+搜索商品列表+商家订单类)

1688商品详情接口是指1688平台提供的API接口&#xff0c;用于获取商品详情信息。通过该接口&#xff0c;您可以获取到商品的详细信息&#xff0c;包括商品标题、价格、库存、描述、图片等。 要使用1688商品详情接口&#xff0c;您需要先申请1688的API权限&#xff0c;并获取ac…...

CentOS服务器网页版Rstudio-server及R包批量安装最佳实践

CentOS服务器安装网页版Rstudio-server及R包批量安装 以下为CentOS 7/8的Rstudio-server安装、配置和R包安装操作 1. 软件包安装 Centos 7安装 # 下载安装包&#xff0c;大小115.14 MB wget -c https://download2.rstudio.org/server/centos7/x86_64/rstudio-server-rhel-…...

centos7内核升级(k8s基础篇)

1.查看系统内核版本信息 uname -r 2.升级内核 2.1更新yum源仓库 yum -y update更新完成后&#xff0c;启用 ELRepo 仓库并安装ELRepo仓库的yum源 ELRepo 仓库是基于社区的用于企业级 Linux 仓库&#xff0c;提供对 RedHat Enterprise (RHEL) 和 其他基于 RHEL的 Linux 发行…...

数据结构与算法设计分析——NP完全理论

目录 一、P类问题与NP类问题的定义二、常见的NP类问题&#xff08;一&#xff09;旅行商问题&#xff08;TSP&#xff09;&#xff08;二&#xff09;哈密尔顿回路问题&#xff08;三&#xff09;判断回路问题&#xff08;四&#xff09;图的着色问题&#xff08;五&#xff09…...

AGNES层次聚类

已知数据集D中有9个数据点&#xff0c;分别是(1,2)&#xff0c;(2&#xff0c;3)&#xff0c;(2,1), (3,1),(2,4),(3,5),(4,3),(1,5),(4,2)。要求&#xff1a; (1)采用层次聚类的聚集算法进行聚类&#xff0c;k2。 (2)距离计算采用欧几里得距离。 (3)簇之间的距离采用单链接方…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

反射获取方法和属性

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

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...