「算法」二分查找1:理论细节
🎇个人主页:Ice_Sugar_7
🎇所属专栏:算法详解
🎇欢迎点赞收藏加关注哦!
二分查找算法简介
- 这个算法的特点就是:细节多,出错率高,很容易就写成死循环
- 有模板,但切记要在理解的基础上记忆,不要死记硬背。有三个模板,一个是本文要讲的简单模板,另外两个分别是查找左、右边界的模板,会在后面的文章中讲解
正文
时间复杂度的推导过程

啥时候用二分算法?
- 能找到某种规律,根据这个规律能找到某个点,以这个点能把区间划分为两块,其中一半区间可以舍弃掉,只需从另一半区间中继续查找
这么说肯定会觉得抽象,没事儿,后面做题慢慢体会
不过现在需要知道:不一定要数据有序才能用二分查找,只要能以某个点将区间分成两段就可以了(简称为“二段性”)
细节
循环结束的条件
- 一开始定义两个指针
left和right,分别指向数组的起始位置和最后一个位置 - 在每次循环中,我们只比较区间中点值 mid 和目标值 target 的大小关系,只知道这两个值,区间中剩下的值是啥仍然未知
- 即使这个区间只剩下一个数,也还是不知道它是谁,此时需要拿它和 target 作比较
所以,当 left > right 时,循环才结束
找区间的中点
由数学知识可得 mid = (left + right)/ 2
但是如果 left 和 right 很大的话,很可能会溢出,所以比较稳妥的写法是 mid = left + (right - left)/ 2,即左端点加上区间长度的一半
如果一共有奇数个元素,那么 mid 就是正中间那个;如果有偶数个,那就有两个中点,上面那两个式子算出来的是靠左边的中点
而如果要找靠右边的中点,只需加个1:mid = (left + right + 1)/ 2 和 mid = 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:理论细节
🎇个人主页:Ice_Sugar_7 🎇所属专栏:算法详解 🎇欢迎点赞收藏加关注哦! 二分查找算法简介 这个算法的特点就是:细节多,出错率高,很容易就写成死循环有模板,但…...
【网络安全】什么样的人适合学?该怎么学?
有很多想要转行网络安全或者选择网络安全专业的人在进行决定之前一定会有的问题: 什么样的人适合学习网络安全?我适不适合学习网络安全? 当然,产生这样的疑惑并不奇怪,毕竟网络安全这个专业在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协议:规定了浏览器发送及服务器返回内容的格式 请求报文:浏览器按照HTTP协议要求的格式,发送给服务器的内容 1.1 请求报文的格式 请求报文的组成部分有: 请求行:请求方法,URL…...
java面试微服务篇
目录 目录 SpringCloud Spring Cloud 的5大组件 服务注册 Eureka Nacos Eureka和Nacos的对比 负载均衡 负载均衡流程 Ribbon负载均衡策略 自定义负载均衡策略 熔断、降级 服务雪崩 服务降级 服务熔断 服务监控 为什么需要监控 服务监控的组件 skywalking 业务…...
JS进阶——垃圾回收机制以及算法
版权声明 本文章来源于B站上的某马课程,由本人整理,仅供学习交流使用。如涉及侵权问题,请立即与本人联系,本人将积极配合删除相关内容。感谢理解和支持,本人致力于维护原创作品的权益,共同营造一个尊重知识…...
【快速解决】python项目打包成exe文件——vscode软件
目录 操作步骤 1、打开VSCode并打开你的Python项目。 2、在VSCode终端中安装pyinstaller: 3、运行以下命令使用pyinstaller将Python项目打包成exe文件: 其中your_script.py是你的Python脚本的文件名。 4、打包完成后,在你的项目目录中会…...
数据结构——lesson3单链表介绍及实现
目录 1.什么是链表? 2.链表的分类 (1)无头单向非循环链表: (2)带头双向循环链表: 3.单链表的实现 (1)单链表的定义 (2)动态创建节点 &#…...
中科大计网学习记录笔记(八):FTP | EMail
前言: 学习视频:中科大郑烇、杨坚全套《计算机网络(自顶向下方法 第7版,James F.Kurose,Keith W.Ross)》课程 该视频是B站非常著名的计网学习视频,但相信很多朋友和我一样在听完前面的部分发现信…...
QPaint绘制自定义坐标轴组件00
最终效果 1.创建一个ui页面,修改背景颜色 鼠标右键->改变样式表->添加颜色->background-color->选择合适的颜色->ok->Apply->ok 重新运行就可以看到widget的背景颜色已经改好 2.创建一个自定义的widget窗口小部件类,class MyChart…...
MATLAB|基于改进二进制粒子群算法的含需求响应机组组合问题研究(含文献和源码)
目录 主要内容 模型研究 1.改进二进制粒子群算法(BPSO) 2.模型分析 结果一览 下载链接 主要内容 该程序复现《A Modified Binary PSO to solve the Thermal Unit Commitment Problem》,主要做的是一个考虑需求响应的机组组合…...
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 之间的关系
继续挖矿,挖“金矿”! 1. Python、conda 和 pip(挖“金矿”工具) Python、conda 和 pip 是在现代数据科学和软件开发中常用的工具,它们各自有不同的作用,但相互之间存在密切的关系: Python&…...
【自然语言处理】实验3,文本情感分析
清华大学驭风计划课程链接 学堂在线 - 精品在线课程学习平台 (xuetangx.com) 代码和报告均为本人自己实现(实验满分),只展示主要任务实验结果,如果需要详细的实验报告或者代码可以私聊博主 有任何疑问或者问题,也欢…...
2.12日学习打卡----初学RocketMQ(三)
2.12日学习打卡 目录: 2.12日学习打卡一. RocketMQ高级特性(续)消息重试延迟消息消息查询 二.RocketMQ应用实战生产端发送同步消息发送异步消息单向发送消息顺序发送消息消费顺序消息全局顺序消息延迟消息事务消息消息查询 一. RocketMQ高级特…...
<网络安全>《35 网络攻防专业课<第一课 - 网络攻防准备>》
1 主要内容 认识黑客 认识端口 常见术语与命令 网络攻击流程 VMWare虚拟环境靶机搭建 2 认识黑客 2.1 白帽、灰帽和黑帽黑客 白帽黑客是指有能力破坏电脑安全但不具恶意目的黑客。 灰帽黑客是指对于伦理和法律态度不明的黑客。 黑帽黑客经常用于区别于一般(正面…...
【实战】一、Jest 前端自动化测试框架基础入门(一) —— 前端要学的测试课 从Jest入门到TDD BDD双实战(一)
文章目录 一、前端要学的测试课1.前端要学的测试2.前端工程化的一部分3.前端自动化测试的例子4.前端为什么需要自动化测试?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"><!-- 左侧内…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
设计模式-3 行为型模式
一、观察者模式 1、定义 定义对象之间的一对多的依赖关系,这样当一个对象改变状态时,它的所有依赖项都会自动得到通知和更新。 描述复杂的流程控制 描述多个类或者对象之间怎样互相协作共同完成单个对象都无法单独度完成的任务 它涉及算法与对象间职责…...
如何在Spring Boot中使用注解动态切换实现
还在用冗长的if-else或switch语句管理多个服务实现? 相信不少Spring Boot开发者都遇到过这样的场景:需要根据不同条件动态选择不同的服务实现。 如果告诉你可以完全摆脱条件判断,让Spring自动选择合适的实现——只需要一个注解,你是否感兴趣? 本文将详细介绍这种优雅的…...
React 样式方案与状态方案初探
React 本身只提供了基础 UI 层开发范式,其他特性的支持需要借助相关社区方案实现。本文将介绍 React 应用体系中样式方案与状态方案的主流选择,帮助开发者根据项目需求做出合适的选择。 1. React 样式方案 1.1. 内联样式 (Inline Styles) 通过 style …...
起重机指挥人员在工作中需要注意哪些安全事项?
起重机指挥人员在作业中承担着协调设备运行、保障作业安全的关键职责,其安全操作直接关系到整个起重作业的安全性。以下从作业前、作业中、作业后的全流程,详细说明指挥人员需注意的安全事项: 一、作业前的安全准备 资质与状态检查ÿ…...
