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

「算法」二分查找1:理论细节

🎇个人主页:Ice_Sugar_7
🎇所属专栏:算法详解
🎇欢迎点赞收藏加关注哦!

二分查找算法简介

  • 这个算法的特点就是:细节多,出错率高,很容易就写成死循环
  • 有模板,但切记要在理解的基础上记忆,不要死记硬背。有三个模板,一个是本文要讲的简单模板,另外两个分别是查找左、右边界的模板,会在后面的文章中讲解

正文

时间复杂度的推导过程
在这里插入图片描述

啥时候用二分算法?

  • 能找到某种规律,根据这个规律能找到某个点,以这个点能把区间划分为两块,其中一半区间可以舍弃掉,只需从另一半区间中继续查找

这么说肯定会觉得抽象,没事儿,后面做题慢慢体会
不过现在需要知道:不一定要数据有序才能用二分查找,只要能以某个点将区间分成两段就可以了(简称为“二段性”)

细节

循环结束的条件

  • 一开始定义两个指针 leftright ,分别指向数组的起始位置和最后一个位置
  • 在每次循环中,我们只比较区间中点值 mid 和目标值 target 的大小关系,只知道这两个值,区间中剩下的值是啥仍然未知
  • 即使这个区间只剩下一个数,也还是不知道它是谁,此时需要拿它和 target 作比较

所以,left > right 时,循环才结束

找区间的中点

由数学知识可得 mid = (left + right)/ 2
但是如果 left 和 right 很大的话,很可能会溢出,所以比较稳妥的写法是 mid = left + (right - left)/ 2,即左端点加上区间长度的一半

如果一共有奇数个元素,那么 mid 就是正中间那个;如果有偶数个,那就有两个中点,上面那两个式子算出来的是靠左边的中点

而如果要找靠右边的中点,只需加个1:mid = (left + right + 1)/ 2mid = left + (right - left + 1)/ 2


简单的二分查找模板

来道简单题,它的答案就是模板:
二分查找

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

模板为:

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

使用时,把省略号处的内容填充上就ok了

相关文章:

「算法」二分查找1:理论细节

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;算法详解 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 二分查找算法简介 这个算法的特点就是&#xff1a;细节多&#xff0c;出错率高&#xff0c;很容易就写成死循环有模板&#xff0c;但…...

【网络安全】什么样的人适合学?该怎么学?

有很多想要转行网络安全或者选择网络安全专业的人在进行决定之前一定会有的问题&#xff1a; 什么样的人适合学习网络安全&#xff1f;我适不适合学习网络安全&#xff1f; 当然&#xff0c;产生这样的疑惑并不奇怪&#xff0c;毕竟网络安全这个专业在2017年才调整为国家一级…...

从零开始学习数据结构—【链表】—【探索环形链的设计之美】

环形链表 文章目录 环形链表1.结构图2.具体实现2.1.环形链表结构2.2.头部添加数据2.2.1.具体实现2.2.2.测试添加数据 2.3.尾部添加数据2.3.1.具体实现2.3.2.添加测试数据 2.4.删除头部数据2.4.1.具体实现2.4.2.测试删除数据 2.5.删除尾部数据2.5.1.具体实现2.5.2.测试删除数据 …...

AJAX——HTTP协议

1 HTTP协议-请求报文 HTTP协议&#xff1a;规定了浏览器发送及服务器返回内容的格式 请求报文&#xff1a;浏览器按照HTTP协议要求的格式&#xff0c;发送给服务器的内容 1.1 请求报文的格式 请求报文的组成部分有&#xff1a; 请求行&#xff1a;请求方法&#xff0c;URL…...

java面试微服务篇

目录 目录 SpringCloud Spring Cloud 的5大组件 服务注册 Eureka Nacos Eureka和Nacos的对比 负载均衡 负载均衡流程 Ribbon负载均衡策略 自定义负载均衡策略 熔断、降级 服务雪崩 服务降级 服务熔断 服务监控 为什么需要监控 服务监控的组件 skywalking 业务…...

JS进阶——垃圾回收机制以及算法

版权声明 本文章来源于B站上的某马课程&#xff0c;由本人整理&#xff0c;仅供学习交流使用。如涉及侵权问题&#xff0c;请立即与本人联系&#xff0c;本人将积极配合删除相关内容。感谢理解和支持&#xff0c;本人致力于维护原创作品的权益&#xff0c;共同营造一个尊重知识…...

【快速解决】python项目打包成exe文件——vscode软件

目录 操作步骤 1、打开VSCode并打开你的Python项目。 2、在VSCode终端中安装pyinstaller&#xff1a; 3、运行以下命令使用pyinstaller将Python项目打包成exe文件&#xff1a; 其中your_script.py是你的Python脚本的文件名。 4、打包完成后&#xff0c;在你的项目目录中会…...

数据结构——lesson3单链表介绍及实现

目录 1.什么是链表&#xff1f; 2.链表的分类 &#xff08;1&#xff09;无头单向非循环链表&#xff1a; &#xff08;2&#xff09;带头双向循环链表&#xff1a; 3.单链表的实现 &#xff08;1&#xff09;单链表的定义 &#xff08;2&#xff09;动态创建节点 &#…...

中科大计网学习记录笔记(八):FTP | EMail

前言&#xff1a; 学习视频&#xff1a;中科大郑烇、杨坚全套《计算机网络&#xff08;自顶向下方法 第7版&#xff0c;James F.Kurose&#xff0c;Keith W.Ross&#xff09;》课程 该视频是B站非常著名的计网学习视频&#xff0c;但相信很多朋友和我一样在听完前面的部分发现信…...

QPaint绘制自定义坐标轴组件00

最终效果 1.创建一个ui页面&#xff0c;修改背景颜色 鼠标右键->改变样式表->添加颜色->background-color->选择合适的颜色->ok->Apply->ok 重新运行就可以看到widget的背景颜色已经改好 2.创建一个自定义的widget窗口小部件类&#xff0c;class MyChart…...

MATLAB|基于改进二进制粒子群算法的含需求响应机组组合问题研究(含文献和源码)

目录 主要内容 模型研究 1.改进二进制粒子群算法&#xff08;BPSO&#xff09; 2.模型分析 结果一览 下载链接 主要内容 该程序复现《A Modified Binary PSO to solve the Thermal Unit Commitment Problem》&#xff0c;主要做的是一个考虑需求响应的机组组合…...

JDBC核心技术

第1章 JDBC概述 第2章 获取数据库连接 第3章 使用PreparedStatement实现CRUD操作 第4章 操作BLOB类型字段 第5章 批量插入 第6章 数据库事务 第7章 DAO及相关实现类 第8章 数据库连接池 第9章 Apache-DBUtils实现CRUD操作图像 小部件...

【天幕系列 02】开源力量:揭示开源软件如何成为技术演进与社会发展的引擎

文章目录 导言01 开源软件如何推动技术创新1.1 开放的创新模式1.2 快速迭代和反馈循环1.3 共享知识和资源1.4 生态系统的建设和扩展1.5 开放标准和互操作性 02 开源软件的商业模式2.1 支持和服务模式2.2 基于订阅的模式2.3 专有附加组件模式2.4 开源软件作为平台模式2.5 双重许…...

“挖矿”系列:细说Python、conda 和 pip 之间的关系

继续挖矿&#xff0c;挖“金矿”&#xff01; 1. Python、conda 和 pip&#xff08;挖“金矿”工具&#xff09; Python、conda 和 pip 是在现代数据科学和软件开发中常用的工具&#xff0c;它们各自有不同的作用&#xff0c;但相互之间存在密切的关系&#xff1a; Python&…...

【自然语言处理】实验3,文本情感分析

清华大学驭风计划课程链接 学堂在线 - 精品在线课程学习平台 (xuetangx.com) 代码和报告均为本人自己实现&#xff08;实验满分&#xff09;&#xff0c;只展示主要任务实验结果&#xff0c;如果需要详细的实验报告或者代码可以私聊博主 有任何疑问或者问题&#xff0c;也欢…...

2.12日学习打卡----初学RocketMQ(三)

2.12日学习打卡 目录&#xff1a; 2.12日学习打卡一. RocketMQ高级特性&#xff08;续&#xff09;消息重试延迟消息消息查询 二.RocketMQ应用实战生产端发送同步消息发送异步消息单向发送消息顺序发送消息消费顺序消息全局顺序消息延迟消息事务消息消息查询 一. RocketMQ高级特…...

<网络安全>《35 网络攻防专业课<第一课 - 网络攻防准备>》

1 主要内容 认识黑客 认识端口 常见术语与命令 网络攻击流程 VMWare虚拟环境靶机搭建 2 认识黑客 2.1 白帽、灰帽和黑帽黑客 白帽黑客是指有能力破坏电脑安全但不具恶意目的黑客。 灰帽黑客是指对于伦理和法律态度不明的黑客。 黑帽黑客经常用于区别于一般&#xff08;正面…...

【实战】一、Jest 前端自动化测试框架基础入门(一) —— 前端要学的测试课 从Jest入门到TDD BDD双实战(一)

文章目录 一、前端要学的测试课1.前端要学的测试2.前端工程化的一部分3.前端自动化测试的例子4.前端为什么需要自动化测试&#xff1f;5.课程涵盖内容6.前置技能7.学习收获 二、Jest 前端自动化测试框架基础入门1. 自动化测试背景及原理前端自动化测试产生的背景及原理 2.前端自…...

蓝桥杯Java组备赛(二)

题目1 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;double sum 0;for(int i0;i<n;i) {int x sc.nextInt()…...

人力资源智能化管理项目(day10:首页开发以及上线部署)

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/humanResourceIntelligentManagementProject 首页-基本结构和数字滚动 安装插件 npm i vue-count-to <template><div class"dashboard"><div class"container"><!-- 左侧内…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...