算法 || 二分查找

目录

二分查找

在排序数组中查找元素的第一个和最后一个位置

搜索插入位置 


 

一个数组经过划分后具有二段性的都可以用二分查找

二分查找

704. 二分查找 - 力扣(LeetCode)

暴力解法:直接遍历数组,找到 target 便返回下标,数组都遍历完了仍找不到,则返回 -1,时间复杂度为 O ( n )(最坏的情况:如果数组中不存在 target,则需要遍历整个数组)。

注意到题目中提供的数组是升序的,即数组从左往右是递增的。我们在数组中随意找个下标,设为 i,

1、如果nums[ i ] > target ,由于数组升序,说明 i 右边的数(即比 nums[ i ] 大的数)一定也大于 target,所以 target 应该落在 i 的左边,我们就不必遍历 i 右边的数了

2、同理,如果nums[ i ] < target ,由于数组升序,说明 i 左边的数(即比 nums[ i ] 小的数)一定也小于 target,所以 target 应该落在 i 的右边,我们就不必遍历 i 左边的数了

3、如果 nums[ i ] == target,那么 i 就是我们想要的返回值

 于是衍生出二分查找, 定义 left、right、mid,

1、如果 nums[ mid ] > target,mid 左边的数不必遍历了,所以 right = mid - 1

2、如果 nums[ mid ] < target,mid 右边的数不必遍历了,所以 left = mid + 1

3、如果 nums[ mid ] == target,说明找到了,返回 mid

4、如果 left > right,说明数组中不存在 target ,返回 -1

要注意 mid 的计算,防止溢出!!

class Solution {
public:int search(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<=right){//int mid=(left+right)/2;int mid=left+(right-left)/2;//防止 left+right 溢出if(nums[mid]>target) right=mid-1;else if(nums[mid]<target) left=mid+1;else { return mid;}}return -1;}
};

在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

 暴力解法:把数组从头到尾遍历一遍,并标记 target 第一次和最后一次出现的下标,时间复杂度为 O(n)。

注意到,题目提供的数组为非递减数组,即 nums[ i ] <= nums[ i+1 ]。

在分析问题之前,我们先区分下面两个 mid 的计算:

int mid=left+(right-left)/2;
int mid=left+(right-left+1)/2;

1、如果 nums[ left ] ~ nums[ right ] 中有奇数个数,mid 的两种计算方法没有区别,都会指向同一个下标;

2、如果 nums[ left ] ~ nums[ right ] 中有偶数个数,mid = left + ( right - left )/2 相当于向下取整,mid = left + ( right - left +1 )/2 相当于向上取整

比如下图,left = 0,right = 5,left + ( right - left )/2 = 2.5,但由于 mid 为 整型,最终 mid 为 2(相当于向下取整);mid = left + ( right - left +1 )/2 = 3(相当于对 2.5 向上取整)。

我们先找 target 第一次出现的下标 begin :begin 下标相当于把数组分为两段,下标 0 ~ begin -1 的数小于 target ,下标为 begin ~ nums.size( ) -1 的数大于等于 target

再找出 target 最后一次出现的下标 end :end 下标也把数组分为两段,下标 0 ~ end 的数小于等于 target,下标为 end+1 ~ nums.size( ) -1 的数大于 target

我们可以根据上面的二段性来找 target 第一个和最后一个位置。

先找 begin,left 从 0 开始,right 从 nums.size( ) -1 开始,

1、如果 nums[ mid ] < target,说明下标小于等于 mid 的数一定小于 target,所以 left = mid + 1

2、如果 nums[ mid ] >= target,说明下标大于 mid 的数一定大于  target,但是下标等于 mid 的数可能大于 target,也可能等于 target,所以 right = mid,如果 right = mid -1 ,那么 nums[ mid ] == target  的情况会被跳过,即可能是第一次出现的下标被跳过了;

3、在找 begin 时,mid = left + ( right - left )/2,因为 mid 向下取整才可以找出在一连串连续出现的  target 中找出第一次出现的下标(相当于整体都靠左边找)

4、left = right 时,while 循环结束,停止寻找,我们需要判断 while 循环结束时 nums[ left ] == target,因为数组中可能不存在 target,如果不存在,可以直接返回 -1 了,没有必要找最后一次出现的下标

 在找 end 位置时,也是相似的道理,

1、如果 nums[ mid ] <= target,说明下标小于等于 mid 的数一定小于等于 target,同样,考虑到下标为 mid 的数可能等于 target,所以 left = mid

2、如果 nums[ mid ] > target,说明下标大于等于 mid 的数一定大于  target,所以 right = mid -1

3、在找 end 时,mid = left + ( right - left +1 )/2,因为 mid 向上取整才可以找出在一连串连续出现的  target 中找出最后一次出现的下标(相当于整体都靠右边找)

TIP:如果  right 的计算中出现了 -1,那么 mid 的计算中就会出现 +1

 

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0) return {-1,-1};int left=0;int right=nums.size()-1;//找左端点while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}int begin=0;if(nums[left]!=target) return {-1,-1};else begin=left;//找右端点left=0;right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target) right=mid-1;else left=mid;}return {begin,right};}
};

搜索插入位置 

35. 搜索插入位置 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/search-insert-position/description/

 同样可以把数组根据 target 分为两段,一边小于 target,一边大于等于 target。

1、如果 nums[ mid ] < target,则 left = mid +1 ;

2、如果 nums[ mid ] >= target,则 right = mid

3、当 left = right 时,退出 while 循环,

a.如果 nums[ left ] < target,说明数组中不存在 target,我们需要把 target 插入到下标为 left +1 的位置中,返回 left +1 ;

b.如果 nums[ left ] > target,同样说明数组中不存在 target,需要把 target 插入到下标为 left 位置中,返回 left;

c.如果 nums[ left ] == target ,说明数组中存在 target,不需要插入,直接返回 left

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}if(nums[left]<target) return left+1;//target比nums[left]大,则在left+1位置插入else return left;//target比nums[left]小,则在left位置插入,若相等,则返回在数组中的下标}
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/314319.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

原型链prototype、__proto、constructor的那些问题整理

再了解原型链之前,我们先来看看构造函数和实例对象的打印结构 - 函数 这里我们定义一个构造函数Fn,然后打印它的结构吧 function Fn(){} console.dir(Fn)控制台得到结构 从上面结构我们能看的出来,函数有两种原型,一种是作为函数特有的原型:prototype,另一种是作为对象的__…

低代码技术的全面应用:加速创新、降低成本

引言 在当今数字化转型的时代&#xff0c;企业和组织面临着不断增长的应用程序需求&#xff0c;以支持其业务运营和创新。然而&#xff0c;传统的软件开发方法通常需要大量的时间、资源和专业技能&#xff0c;限制了企业快速响应市场变化和业务需求的能力。在这样的背景下&…

chrome浏览器安装elasticsearch的head可视化插件

head插件简介 elasticsearch-head被称为是弹性搜索集群的web前端&#xff0c;head插件主要是用来和elastic Cluster交互的Web前端 head插件历史 elasticsearch-head插件在0.x-2.x版本的时候是集成在elasticsearch内的&#xff0c;由elasticsearch的bin/elasticsearch-plugin…

区块链 | OpenSea 相关论文:Toward Achieving Anonymous NFT Trading(一)

​ &#x1f951;原文&#xff1a; Toward Achieving Anonymous NFT Trading &#x1f951;写在前面&#xff1a; 本文对实体的介绍基于论文提出的方案&#xff0c;而非基于 OpenSea 实际采用的方案。 其实右图中的 Alice 也是用了代理的&#xff0c;不过作者没有画出来。 正文…

基于SpringBoot + Vue实现的校园(通知、投票)管理系统设计与实现+毕业论文(12000字)+答辩PPT+指导搭建视频

目录 项目介绍 运行环境 技术栈 效果展示 论文展示 总结 项目介绍 本系统包含管理员、用户、院校管理员三个角色。 管理员角色&#xff1a;用户管理、院校管理、单位类别管理、院校管理员管理、单位管理、通知推送管理、投票信息管理、通知回复管理等。 用户角色&#…

sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

数据结构—单链表

含义 1.顺序表的回顾 之前的文章已经谈到了顺序表&#xff0c;关于顺序表&#xff0c;有一下的几种特点 1.中间&#xff0c;头部的删除&#xff0c;复杂度为O(N); 2.增容会有申请新的空间&#xff0c;拷贝数据&#xff0c;释放旧的空间&#xff0c;会有不小的消耗&#xff…

数据结构:最小生成树(Prim算法和Kruskal算法)、图的最短路径(Dijkstra算法和Bellman-Ford算法)

什么是最小生成树&#xff1f;Prim算法和Kruskal算法是如何找到最小生成树的&#xff1f; 最小生成树是指在一个连通图中&#xff0c;通过连接所有节点并使得总权重最小的子图。 Prim算法和Kruskal算法是两种常用的算法&#xff0c;用于寻找最小生成树。 Prim算法的步骤如下&…

mysql的多表查询和子查询

多表查询&#xff1a;查询数据时&#xff0c;需要使用多张表来查询 多表查询分类&#xff1a; 1.内连接查询 2.外连接查询 3.子查询 笛卡尔积&#xff1a; create table class (id int primary key auto_increment,name varchar(10) ); create table student (id int primar…

学习STM32第十六天

RTC实时时钟 一、简介 RTC是一个独立的BCD格式定时器&#xff0c;提供一个时钟日历&#xff0c;两个可编程报警中断&#xff0c;一个具有中断功能周期性可编程唤醒标志&#xff0c;RTC和时钟配置系统处于后备区域。 通过两个32位寄存器以BCD格式实现秒、分钟、小时&#xff08…

stable-diffusion-webui安装与使用过程中的遇到的error合集

stable-diffusion-webui1.9.2踩坑安装 1. 安装过程1.1 stable-diffusion-webui1.2 在win11或win10系统安装&#xff0c;需修改两个启动脚本1.2.1 修改webui-user.bat1.2.2 修改webui.bat 1.3 双击 webui-user.bat 启动脚本1.3.1 no module xformers. Processing without on fre…

Grafana系列 | Grafana监控TDengine库数据 |Grafana自定义Dashboard

开始前可以去grafana官网看看dashboard文档 https://grafana.com/docs/grafana/latest/dashboards 本文主要是监控TDengine库数据 目录 一、TDengine介绍二、Grafana监控TDengine数据三、Grafana自定义Dashboard 监控TDengine库数据1、grafana 变量2、添加变量3、配置panel 一…

FSMC读取FPGA的FIFO

一、硬件说明 FSMC配置 单片机的代码如下&#xff1a; #define VALUE_ADDRESS_AD1 (__IO uint16_t *)0x60400000while (1){if(!HAL_GPIO_ReadPin(GPIOF, GPIO_PIN_8)) //数据非空{data *(__IO uint16_t *)VALUE_ADDRESS_AD1;data2 *(__IO uint16_t *)VALUE_ADDRESS_AD1…

【数据库】MongoDB

文章目录 [toc]数据库操作查询数据库切换数据库查询当前数据库删除数据库查询数据库版本 数据集合操作创建数据集合查询数据集合删除数据集合 数据插入插入id重复的数据 数据更新数据更新一条丢失其他字段保留其他字段 数据批量更新 数据删除数据删除一条数据批量删除 数据查询…

Transformer step by step--Positional Embedding 和 Word Embedding

Transformer step by step往期文章&#xff1a; Transformer step by step--层归一化和批量归一化 要把Transformer中的Embedding说清楚&#xff0c;那就要说清楚Positional Embedding和Word Embedding。至于为什么有这两个Embedding&#xff0c;我们不妨看一眼Transformer的…

Hadoop之路

hadoop更适合在liunx环境下运行&#xff0c;会节省后期很多麻烦&#xff0c;而用虚拟器就太占主机内存了&#xff0c;因此后面我们将把hadoop安装到wsl后进行学习,后续学习的环境是Ubuntu-16.04 &#xff08;windows上如何安装wsl&#xff09; 千万强调&#xff0c;有的命令一…

【24年物联网华为杯】赛题分析与初步计划

赛事介绍 官网链接&#xff1a;2024 年全国大学生物联网设计竞赛 (sjtu.edu.cn) 含金量&#xff1a;属于A类赛事 &#xff08;注意&#xff1a;很多搜索结果的序号是按照选入时间排列的&#xff0c;与含金量无关&#xff0c;华为杯是23年选入的&#xff09; Kimi Chat: 全国…

JavaScript创建和填充数组的更多方法

空数组fill()方法创建并填充数组 ● 我们之前创建数组的方式都是手动去创建去一个数据&#xff0c;例如 console.log([1, 2, 3, 4, 5, 6, 7]);● 当然我们也可以使用Array对象来构造数组 console.log([1, 2, 3, 4, 5, 6, 7]); console.log(new Array(1, 2, 3, 4, 5, 6, 7));…

Java毕业设计 基于SpringBoot vue城镇保障性住房管理系统

Java毕业设计 基于SpringBoot vue城镇保障性住房管理系统 SpringBoot 城镇保障性住房管理系统 功能介绍 首页 图片轮播 房源信息 房源详情 申请房源 公示信息 公示详情 登录注册 个人中心 留言反馈 后台管理 登录 个人中心 修改密码 个人信息 用户管理 房屋类型 房源信息管理…

【算法基础实验】图论-UnionFind连通性检测之quick-find

Union-Find连通性检测之quick-find 理论基础 在图论和计算机科学中&#xff0c;Union-Find 或并查集是一种用于处理一组元素分成的多个不相交集合&#xff08;即连通分量&#xff09;的情况&#xff0c;并能快速回答这组元素中任意两个元素是否在同一集合中的问题。Union-Fin…