【算法】——二分查找合集

8e19eee2be5648b78d93fbff2488137b.png

阿华代码,不是逆风,就是我疯

你们的点赞收藏是我前进最大的动力!!

希望本文内容能够帮助到你!!

目录

零:二分查找工具

1:最基础模版

2:mid落点问题

一:最简单的二分

二:查找元素的位置(可能会有多个)

三:搜索插入位置

四:x的平方根

五:山脉数组的峰顶索引

六:寻找峰值

​编辑

解法一

解法二

 七:点名


零:二分查找工具

1:最基础模版

mid的写法可以防止溢出

2:mid落点问题

巧妙记忆:循环条件为while(left<right)时,left = mid,想象一下,只剩下两个球,那么我们的mid只能落在右端点,否则left = mid 会造成 left < right 死循环,此时我们确定的是右边的界限

重点:left 和right 根据题目的意思进行设置,然后才是mid的设置根据left和right的设置而设置(这才是这个二分查找的精髓所在)

简单记忆:落在哪个端点确定哪个界限

一:最简单的二分

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

class Solution {public int search(int[] nums, int target) {//mid=left + (right - left)/3//用left移动思想来确定mid的位置,这种写法可以防溢出int left = 0 , right = nums.length-1 , mid = (left+right)/2;while(left<=right){if(nums[mid] < target){left = mid + 1 ;mid = (left+right)/2;}else if(nums[mid] > target){right = mid - 1;mid = (left+right)/2;}else{return mid;}}return -1;}
}

二:查找元素的位置(可能会有多个)

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

class Solution {public int[] searchRange(int[] nums, int target) {int[] result = new int[]{-1,-1};if(nums.length == 0 ){return result;}//左端点int left = 0 , right = nums.length-1 ,targetLeft = 0 , targetRight = 0;while(left < right){int mid = left + (right - left )/2;if(nums[mid] < target){left = mid + 1;}else{right = mid;}}targetLeft = left;left = 0 ; right = nums.length-1 ;//右端点while(left < right){int mid = left + (right-left+1)/2;if(nums[mid] > target){right = mid - 1;}else{left = mid;}}targetRight = right;if(nums[targetLeft] != target){return result;}else if(nums[targetLeft] == nums[targetRight]){result[0] = targetLeft;result[1] = targetRight;return result;}else{}return result;}
}

三:搜索插入位置

35. 搜索插入位置 - 力扣(LeetCode)

class Solution {public int searchInsert(int[] nums, int target) {if(nums.length == 0){return 0;}int targetLeft = 0  , n = nums.length;int left = 0 , right = nums.length-1;//这道题只用找一个左界限就够了//左界限left = 0 ; right = n-1;while(left < right){int mid = left + (right - left)/2;//左端点if(nums[mid] >= target){right = mid;}else{left = mid + 1;}} targetLeft = left;int result = 0;if(target > nums[targetLeft]){result = targetLeft + 1;}else{result = targetLeft ;}return result;}
}

四:x的平方根

69. x 的平方根 - 力扣(LeetCode)

class Solution {public int mySqrt(int x) {long left = 0 , right = x ;if(x < 1 ){return 0;}long mid = 0;//mid的平方越界了while(left < right){mid = left + (right - left + 1)/2;if(mid * mid <= x){left = mid;}else{right = mid - 1 ;}}return (int)left;//强转为int类型}
}

五:山脉数组的峰顶索引

852. 山脉数组的峰顶索引 - 力扣(LeetCode)

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 0 , right = arr.length , n = arr.length;while(left < right){int mid = left + (right - left + 1)/2;if(arr[mid] > arr[mid-1]){left = mid;}else if(arr[mid] < arr[mid-1]){right = mid - 1;}else{}}return left;}
}

六:寻找峰值

162. 寻找峰值 - 力扣(LeetCode)

解法一

class Solution {public int findPeakElement(int[] nums) {int left = 0 , right = nums.length-1;//如果数组中只有一个元素,while循环都进不去,规避了这个问题nbwhile(left < right){int mid = left + (right - left )/2;if(nums[mid+1] > nums[mid]){left = mid + 1;}else if(nums[mid+1] < nums[mid]){right = mid;}else{}}return left;}
}

解法二

class Solution {public int findPeakElement(int[] nums) {//暴力解法int n = nums.length , result = 0;if(n == 1){result = 0;}else if(nums[0] > nums[1]){result = 0;}else if(nums[n-1] > nums[n-2]){result = n-1;}else{int left = 0 , right = nums.length ;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid] > nums[mid-1]){left = mid;}else if(nums[mid] < nums[mid-1]){right = mid-1;}else{}}result = left;}return result;}
}

七:寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

class Solution {public int findMin(int[] nums) {int left = 0 , n = nums.length , right = n-1;int tem = nums[n-1];while(left < right){int mid = left + (right - left)/2;if(nums[mid] <= nums[n-1]){right = mid;}else{left = mid + 1;}}return nums[left];}
}

 七:点名

LCR 173. 点名 - 力扣(LeetCode)

class Solution {public int takeAttendance(int[] records) {int left = 0 , n = records.length , right = records.length-1;if(records[0] != 0){return 0;}if(records[n-1] == n-1){return n;}while(left < right){int mid = left + (right - left)/2;if(records[mid] - mid <= 0){left = mid + 1;}else{right = mid ;}}return right;}
}

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

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

相关文章

读数据质量管理:数据可靠性与数据质量问题解决之道03数据目录

1. 同步数据 1.1. 不同的数据仓库和数据湖通过数据集成层来进行桥接 1.2. AWS Glue、Fivetran和Matillion等数据集成工具从不同来源收集数据&#xff0c;统一这些数据&#xff0c;并将其转换为上游来源 1.3. 数据集成的一个典型用例是收集数据湖的数据并以结构化格式将其加载…

openSUSE 环境下通过 zypper 安装软件

操作场景 为了提升您在云服务器上的软件安装效率&#xff0c;减少下载和安装软件的成本&#xff0c;腾讯云提供了 zypper 下载源。openSUSE 操作系统和部分 SLES 的云服务器用户可通过 zypper 快速安装软件。本文档以 openSUSE 操作系统为例&#xff0c;指导您通过 zypper 快速…

ima.copilot-腾讯智能工作台

一、产品描述 ima.copilot是腾讯推出的基于腾讯混元大模型技术的智能工作台&#xff0c;通过先进的人工智能技术&#xff0c;为用户提供了一个全新的搜读写体验&#xff0c;让知识管理变得更加智能和高效。它不仅是一个工具&#xff0c;更是一个智能的伙伴&#xff0c;能够帮助…

NVIDIA Isaac Sim 仿真平台体验测评

目录 一、引言二、GPU加速相关体验2.1 Isaac Sim GPU 加速体验2.2 GPU加速体验分析 三、AI框架集成相关体验四、学术研究价值五、开发生态六、综合分析6.1 主要优势6.1.1 仿真效率6.1.2 开发便利性6.1.3 与 AI 框架的协同性 6.2 潜在应用场景 七、运行体验与建议7.1 GPU加速与P…

WebRTC API分析

主题 本文详细描述常用的webrtc api 媒体协商类 myPeerConnection.createOffer([options]); var options { offerToReceiveAudio: true, // 告诉另一端&#xff0c;你是否想接收音频&#xff0c;默认true offerToReceiveVideo: true, // 告诉另一端&a…

11张思维导图带你快速学习java

博主主页:【南鸢1.0】 本文专栏&#xff1a;JAVA 本文目录 简介 1.Java SE​编辑 2.Java Web 3.MySQL​编辑 4.前端技术 5.Linux 6.Spring SpringMvc mybatis 7.JVM 8.Springboot 9.Vue 10.SpringCloud 11.常用中间件 总结 简介 Java是一种跨平台的编程语言&am…

Jmeter基础篇(22)服务器性能监测工具Nmon的使用

一、前言 我们在日常做压测的过程中&#xff0c;不仅仅需要监控TPS&#xff0c;响应时间&#xff0c;报错率等这些系统基础性能数据&#xff0c;还需要对服务器的性能&#xff08;如CPU、磁盘、内存、网络IO等&#xff09;做监控&#xff0c;以求对系统运行过程中的硬件性能有…

Unity3D学习FPS游戏(12)敌人检测和攻击玩家

前言&#xff1a;上一篇实现了敌人能动&#xff0c;有了点乐趣&#xff0c;但是敌人和玩家没什么对抗性。本篇将实现敌人追击玩家&#xff0c;并攻击玩家。 敌人攻击玩家 敌人检测玩家目标思路-碰撞检测的Trigger触发实现 敌人攻击目标思路-模仿玩家发射子弹的思路实现 效果 敌…

利用滑动窗口解题

目录 前言&#xff1a; 第一题&#xff1a;209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 第二题&#xff1a;1004. 最大连续1的个数 III - 力扣&#xff08;LeetCode&#xff09; 第三题&#xff1a;3. 无重复字符的最长子串 - 力扣&#xff08;LeetCode&…

车载空气净化器语音芯片方案

开发背景&#xff1a; 随着人们生活质量的不断提升和环保意识的日益增强&#xff0c;车内空气质量成为了广大车主关注的焦点。长时间封闭的车厢环境&#xff0c;加之城市空气污染、新车内饰材料释放的有害气体等因素&#xff0c;使得车内空气质量往往不尽如人意&#xff0c;严重…

《MYSQL45讲》误删数据怎么办

对误删数据分类的话&#xff0c;有 1.delete 误删行 2.drop table 或者truncate table 语句误删表 3.使用drop database 误删数据库 4.使用rm命令误删整个MYSQL实例 一&#xff0c;误删行 一下操作前置条件是&#xff1a;binlog的格式是row&#xff0c;并且binglog_row_im…

不对称信息

你买了一辆二手车&#xff0c;你并不知道它出过几次事故&#xff0c;但它之前的车主却对此了如指掌。来买保险的公司都是那些出险概率很大的&#xff08;比如矿工、化工厂&#xff09;&#xff0c;但那些安全的公司很少去买保险&#xff0c;这两种问题都属于信息不对称问题。 …

94个属于一区且接受医工交叉领域投稿的期刊汇总|个人观点·24-11-13

小罗碎碎念 继汇总病理AI的基础模型、病理组学&影像组学的公开数据集以后&#xff0c;我们再来盘一盘医工交叉领域有哪些热门期刊可以投稿。我会分区进行介绍&#xff0c;每个区则会进一步划分学科种类&#xff0c;方便大家选择适合自己的投稿期刊。 这期推文先分享大类属…

网站小程序app怎么查有没有备案?

网站小程序app怎么查有没有备案&#xff1f;只需要官方一个网址就可以&#xff0c;工信部备案查询官网地址有且只有一个&#xff0c;百度搜索 "ICP备案查询" 找到官方gov.cn网站即可查询&#xff01; 注&#xff1a;网站小程序app备案查询&#xff0c;可通过输入单位…

MySQL45讲 第二十讲 幻读是什么,幻读有什么问题?

文章目录 MySQL45讲 第二十讲 幻读是什么&#xff0c;幻读有什么问题&#xff1f;一、幻读的定义二、幻读带来的问题&#xff08;一&#xff09;语义问题&#xff08;二&#xff09;数据一致性问题 三、InnoDB 解决幻读的方法四、总结 MySQL45讲 第二十讲 幻读是什么&#xff0…

FatLab:我的编程课程系列

FatLab 是一款教程类软件。 大概是因为我的编程生涯始于自学&#xff0c;FatLab便也保持了这种气息&#xff1a;从一个“自然生长”的角度提供了一套C语言教程。 教程方面&#xff0c;目前仅完成了《C语言基础要素》系列。正如其名&#xff0c;这个系列仅探讨了语言中非常基础…

冗余连接2 hard题 代随C#写法

此题在卡码网109与力扣685题亦有记载 有一说一C#写法我没咋搞懂 就看明白了思路 这里贴一个答案待后续我醒悟了再来看罢 难就难在对整体数据结构classUnion&#xff08;并查集&#xff09;的理解不熟并且 对于输入输出这个迭代过程理解上也比较吃力 109. 冗余连接II 题…

【QT】QSS

个人主页~ 一、QSS QSS可以说是拿了CSS的一部分过来用&#xff0c;是CSS的简化版本 1、基本语法 选择器 {属性名:属性值; }将界面上所有的QPushButton文本颜色都改为红色 QPushButton {color:red; }2、设置方式 &#xff08;1&#xff09;指定控件样式设置 在widget.cpp中…

java模拟键盘实现selenium上下左右键 table中的左右滚动条实现滚动

在这篇文章中&#xff0c;我们将学习如何使用Java编程语言模拟键盘输入&#xff0c;特别是模拟上下左右方向键的操作。这是一个很有趣的项目&#xff0c;尤其适合刚入行的开发者。我们将分步进行&#xff0c;接下来&#xff0c;我们会通过表格展示整个实现过程&#xff0c;然后…

JQuery封装的ajax

1. 注意&#xff1a; 首先要导jq的包json对象可以用 . 来调用keyjava只能给前端传页面&#xff0c;或者打印的内容String jsonstr json.toJSONString(resultJSON); //将对象转为JSON对象 Json格式和参数解释&#xff1a; <script src"js/jquery-1.10.2.min.js&quo…