当前位置: 首页 > 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"><!-- 左侧内…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

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

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

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...