“二分”带来“十分”快感——二分思想的奥秘解析
文章目录
- 无处不在的二分思想
- 二分查找惊人的查找速度
- 二分查找的递归与非递归实现
- 1.循环退出条件
- 2.mid的取值
- 3.low和high的更新
- 最后说一句
🐱🐉作者简介:大家好,我是黑洞晓威,一名大二学生,希望和大家一起进步。
👿本文收录于 算法,本专栏是针对大学生、初学算法的人准备,解析常见的数据结构与算法,同时备战蓝桥杯。
无处不在的二分思想
二分查找是一种非常简单易懂的快速查找算法,生活中到处可见。比如说,我们现在来做一个猜字游戏。我随机写一个0到99之间的数字,然后你来猜我写的是什么。猜的过程中,你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。你来想想,如何快速猜中我写的数字呢?
假设我写的数字是23,你可以按照下面的步骤来试一试。(如果猜测范围的数字有偶数个,中间数有两个,就选择较小的那个。)

7次就猜出来了,是不是很快?这个例子用的就是二分思想,按照这个思想,即便我让你猜的是0到999的数字,最多也只要10次就能猜中。不信的话,你可以试一试。

看懂这两个例子,你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下, 二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
二分查找惊人的查找速度
二分查找是一种非常高效的查找算法,高效到什么程度呢?我们来分析一下它的时间复杂度。
我们假设数据大小是n,每次查找后数据都会缩小为原来的一半,也就是会除以2。最坏情况下,直到查找区间被缩小为空,才停止。

可以看出来,这是一个等比数列。其中n/2k=1时,k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了k次区间缩小操作,时间复杂度就是O(k)。通过n/2k=1,我们可以求得k=log2n,所以时间复杂度就是O(logn)。
因为logn是一个非常“恐怖”的数量级,即便n非常非常大,对应的logn也很小。比如n等于2的32次方,这个数很大了吧?大约是42亿。也就是说,如果我们在42亿个数据中用二分查找一个数据,最多需要比较32次。
二分查找的递归与非递归实现
实际上,简单的二分查找并不难写,注意我这里的“简单”二字。讲到二分查找的变体问题,那才是真正烧脑的。今天,我们来看如何来写最简单的二分查找。
最简单的情况 就是 有序数组中不存在重复元素,我们在其中用二分查找值等于给定值的数据。我用Java代码实现了一个最简单的二分查找算法。
public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (a[mid] == value) {return mid;} else if (a[mid] < value) {low = mid + 1;} else {high = mid - 1;}}return -1;
}
这个代码我稍微解释一下,low、high、mid都是指数组下标,其中low和high表示当前查找的区间范围,初始low=0, high=n-1。mid表示[low, high]的中间位置。我们通过对比a[mid]与value的大小,来更新接下来要查找的区间范围,直到找到或者区间缩小为0,就退出。如果你有一些编程基础,看懂这些应该不成问题。现在,我就着重强调一下 容易出错的3个地方。
1.循环退出条件
注意是low<=high,而不是low<high。
2.mid的取值
实际上,mid=(low+high)/2这种写法是有问题的。因为如果low和high比较大的话,两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high-low)/2。更进一步,如果要将性能优化到极致的话,我们可以将这里的除以2操作转化成位运算low+((high-low)>>1)。因为相比除法运算来说,计算机处理位运算要快得多。
3.low和high的更新
low=mid+1,high=mid-1。注意这里的+1和-1,如果直接写成low=mid或者high=mid,就可能会发生死循环。比如,当high=3,low=3时,如果a[3]不等于value,就会导致一直循环不退出。
如果你留意我刚讲的这三点,我想一个简单的二分查找你已经可以实现了。 实际上,二分查找除了用循环来实现,还可以用递归来实现,过程也非常简单。
我用Java语言实现了一下这个过程,正好你可以借此机会回顾一下写递归代码的技巧。
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {return bsearchInternally(a, 0, n - 1, val);
}private int bsearchInternally(int[] a, int low, int high, int value) {if (low > high) return -1;int mid = low + ((high - low) >> 1);if (a[mid] == value) {return mid;} else if (a[mid] < value) {return bsearchInternally(a, mid+1, high, value);} else {return bsearchInternally(a, low, mid-1, value);}
}
最后说一句
感谢大家的阅读,文章通过网络资源与自己的学习过程整理出来,希望能帮助到大家。
才疏学浅,难免会有纰漏,如果你发现了错误的地方,可以提出来,我会对其加以修改。

相关文章:
“二分”带来“十分”快感——二分思想的奥秘解析
文章目录无处不在的二分思想二分查找惊人的查找速度二分查找的递归与非递归实现1.循环退出条件2.mid的取值3.low和high的更新最后说一句🐱🐉作者简介:大家好,我是黑洞晓威,一名大二学生,希望和大家一起进…...
一台服务器最大能支持多少条 TCP 连接?问倒一大片。。。
一台服务器最大能打开的文件数 限制参数 我们知道在Linux中一切皆文件,那么一台服务器最大能打开多少个文件呢?Linux上能打开的最大文件数量受三个参数影响,分别是: fs.file-max (系统级别参数)…...
蓝桥杯嵌入式RTC实时时钟
文章目录 前言一、RTC是什么二、cubemx的配置三、函数的使用总结前言 本篇文章将给大家介绍RTC实时时钟。 一、RTC是什么 STM32的实时时钟RTC是一个独立的定时器,RTC时钟内部依靠BCD码计数。RTC实时时钟提高时钟、闹钟、日历功能。RTC功耗较低,可以使用在低功耗设备上。 …...
Centos7 挂载 ISO镜像
切到mnt目录:cd /mnt mkdir iso确保centos镜像在服务上存在,磁盘挂载mount -o loop /home/xx.iso /mnt/iso查看是否挂载成功df -h出现红色的部分表示挂载成功修改源切目录并修改yum源:cd /etc/yum.repos.dllvim Centos-Base.repo修改后yum clean allyum list安装lrz…...
三级数据库备考--数据库应用系统开发方法第一次练习(刷题库知识点记录)
1.数据库的三级模式由外模式、模式、内模式构成。外模式是用户可见的部分数据的存在形式;模式可以等价为全体数据的逻辑结构且用户不可见,是三级模式的中间部分;内模式对应数据库的物理结构和存储方式。当模式改变时,由数据库管理…...
免费空间主机是什么?怎么申请免费空间主机
随着网络的普及,越来越多的人开始使用免费空间。这种新的商业模式也让一些商家得以获利。 1:免费空间的概念 免费空间是指允许您自由使用的网络服务。这意味着它可以被任何人用来创建、编辑和发布网站内容或应用程序,而无需考虑任何付费业务协…...
网络安全文章汇总导航(持续更新)
网络安全文章汇总导航(持续更新)1.基础篇(已完结):2.工具篇(持续更新):3.靶场安装(持续更新,但不确定):4.权限提升(持续更…...
AI-TestOps —— 软件测试工程师的一把利剑
写在前面软件测试的前世今生测试工具开始盛行AI-TestOps 云平台● AI-TestOps 功能模块● AI-TestOps 自动化测试流程写在前面 最近偶然间看到一句话:“软件测试是整个 IT 行业中最差的岗位”。这顿时激起了我对软件测试领域的兴趣,虽然之前未涉及过软件…...
Linux内核进程管理原理详解
前言:Linux内核里大部分都是C语言。建议先看《Linux内核设计与实现(Linux Kernel Development)》,Robert Love,也就是LKD。Linux是一种动态系统,能够适应不断变化的计算需求。Linux计算需求的表现是以进程的通用抽象为中心的。进程可以是短期…...
通过Linux串口实现树莓派与电脑通信
目录 一 串口说明 二 USB—TTL模块 ● usb-ttl模块接口 三 串口通信常用的API 四 修改串口的配置文件 五 串口通信代码验证 ● 发送一个字符/字符串到串口 ● 树莓读取串口数据(字符) ● 代码拓展(双方) 一 串口…...
全球变暖 蓝桥杯 178
题目描述你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示:........##.....##........##...####....###........其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座…...
Java现在好找工作吗?
Java到2023年已经28岁了,可能你会怀疑它是否还一如当年一样的强大,在应用层领域独占鳌头。但是基于Java庞大的市场占有率和需求,它依然在保持着更新迭代,依然是最常用的底层开发语言,基于其安全性、开放性、稳定性和跨…...
Flink 第1章 基础介绍和特性
一 Flink概念 1.1 Flink的概念 Flink是一个框架和分布式处理引擎,用于对无界和有解数据流进行状态计算。如下图所示: 1.2 Flink的应用场景 1.3 Flink的目标 1.高吞吐量 2.低延迟 3,结果的准确性和良好的容错性。 1.4 Flink与spark的区别…...
docker 安装 nginx无坑版
一. 拉取镜像 docker pull nginx二. 创建挂载目录 mkdir -p /usr/local/nginx/conf mkdir -p /usr/local/nginx/log mkdir -p /usr/local/nginx/html三. 从nginx容器里复制nginx的配置文件到主机里 创建个容器 docker run --name nginx -p 80:80 -d nginx将容器内的配置文件…...
自己动手做chatGPT:向量的概念和相关操作
chatGPT的横空出世给人工智能注入一针强心剂,它是历史上以最短时间达到一亿用户的应用。chatGPT的能力相当惊人,它可以用相当流利的语言和人对话,同时能够对用户提出的问题给出相当顺畅的答案。它的出现已经给各个行业带来不小冲击࿰…...
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(7)
目录 写在前面: 题目:P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: …...
Python嵌套函数(Nested function)和闭包(closure)
Python嵌套函数(Nested function)和闭包(closure) 闭包(closure)是建立在嵌套函数基础上的,是一种特殊的嵌套函数结构。 先看嵌套函数(Nested function)。 Python允许…...
【实战】React 必会第三方插件 —— Cron 表达式生成器(qnn-react-cron)
文章目录一、引子二、配置使用1.安装2.使用(1)直接调用(2)赋值到表单(Form)(3)自定义功能按钮(4)隐藏指定 Tab(5)其他三、常见问题及解…...
C# 教你如何终止Task线程
我们在多线程中通常使用一个bool IsExit类似的代码来控制是否线程的运行与终止,其实使用CancellationTokenSource来进行控制更为好用,下面我们将介绍CancellationTokenSource相关用法。C# 使用 CancellationTokenSource 终止线程使用CancellationTokenSo…...
整合SpringCache
整合SpringCache 1、引入依赖cache还有redis <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-cache</artifactId> </dependency>2、写配置 spring:cache:type: redis3、测试使用缓存 Cache…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
