二分查找算法详讲(三种版本写法)原创
介绍:
二分查找算法(Binary Search)是一种在有序数组中查找目标元素的算法。
它的基本思想是通过将目标元素与数组的中间元素进行比较,从而将搜索范围缩小一半。
- 如果目标元素等于中间元素,则搜索结束;
- 如果目标元素小于中间元素,则继续在左半部分查找;
- 如果目标元素大于中间元素,则在右半部分查找。
通过不断地将搜索范围缩小一半,最终可以找到目标元素或确定目标元素不存在。
接下来通过例题介绍二分的不同写法
例题:
输入一个整数 n, 接下来一行输入 n 个整数(保证整数序列有序), 最后输入一个整数 m, 查找 m 在序列中的起始下标和结束下标
示例1:
输入:
5
1 2 2 4 5
2
输出:
1 2
解释:
2 在序列中的起始和结束位置是下标 1 和 2
代码讲解:
二分代码按照退出条件分为
- while (l <= r)
- while (l < r)
代码中的所有 l 和 r 都是序列的左右闭区间
代码中的所有 l + r >> 1 和 l + r + 1 >> 1 分别相当于 (l + r) / 2 和 (l + r + 1) / 2。>>是按位右移, 整数向右位移一位相当于除2
代码中的所有 x, 都是目标值, 也就是要查找的值; 所有的 idx, 是答案, 也就是要查找数的起始下标或结束下标
先讲第一种: while (l <= r), 在l > r时退出
// 查找起始下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1; // 如果当前中间值比 x 小, 需要去序列的右区间, 因为mid位置的数比 x 小, 那么左边的区间(l, mid]的所有数都比 x 小else if (a[mid] > x) r = mid - 1; // 同上else if (a[mid] == x) // 等于答案时{idx = mid;r = mid - 1; // 我们要找的时起始的下标, 虽然此时a[mid] == x, 但是mid的左边可能还有等于x的值, 所以我们要继续往左区间去找}
}// 查找结束下标(代码中只有注释的地方和上面的代码不一样)
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1; else if (a[mid] > x) r = mid - 1; else if (a[mid] == x) {idx = mid;l = mid + 1; // 我们要找的时结束的下标, 虽然此时a[mid] == x, 但是mid的右边可能还有等于x的值, 所以我们要继续往右区间去找}
}
观察上面代码我们可以把a[mid] == x的情况跟其他两种情况合并
// 查找起始下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1; else if (a[mid] >= x){idx = mid;r = mid - 1; // 继续往左区间找}
}// 查找结束下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;if (a[mid] <= x){idx = mid;l = mid + 1; // 继续往右区间找}else if (a[mid] > x) r = mid - 1;
}
下面讲第二种: while (l < r) 在l == r时退出
大家可以发现这种写法不需要 idx 这个变量来记录最终查找的x的起始下标或结束下标了, 因为最后l就是对应的起始下标或结束下标。(r等于l, 所以用r也行)
查找起始下标
int l = 0, r = n - 1;
while (l < r)
{int mid = l + r >> 1; // 区间分成了两个 [l, mid] 和 (mid, r]if (a[mid] < x) l = mid + 1;// 当a[mid] == x的时候, r一直往左, 所以当有多个相同的x的话, 会查找到第一个else if (a[mid] >= x) r = mid; // 因为a[mid]可能 == x, 因为mid也可能满足条件, 所以区间变成[l, mid]
}查找结束下标
int l = 0, r = n - 1, idx = 0;
while (l < r)
{ int mid = l + r + 1 >> 1; // 区间分成了两个 [l, mid) 和 [mid, r]if (a[mid] > x) r = mid - 1;// 当a[mid] == x的时候, l一直往右, 所以当有多个相同的x的话, 会查找到最后一个else if (a[mid] <= x) l = mid; // 因为a[mid]可能 == x, 因为mid也可能满足条件, 所以区间变成[mid, r]
}
接下来讲一下第二种查找结束下标的时候 为什么是 mid = l + r + 1 >> 1,而不是 mid = l + r >> 1;
c++默认向0取整, 对于正整数你可以说是向下取整, 也就是 5 / 2 = 2,
当出现 l = r - 1 的时候, 此时 mid = (l + r) / 2 向下取整后等于 r - 1 , 如果此时进入了a[mid] <= x的分支, 那么 l = mid = r - 1, 这时会发现 l 没有发生变化, 那么就会一直陷入死循环
先更到这里, 后面再补充
觉得写的不错的话, 点个赞吧
相关文章:
二分查找算法详讲(三种版本写法)原创
介绍: 二分查找算法(Binary Search)是一种在有序数组中查找目标元素的算法。 它的基本思想是通过将目标元素与数组的中间元素进行比较,从而将搜索范围缩小一半。 如果目标元素等于中间元素,则搜索结束;如果目标元素小…...
Git钩子(Hooks)之commit之前自动执行脚本
介绍 官方文档: 英文:https://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks中文:https://git-scm.com/book/zh/v2/自定义-Git-Git-钩子 下面只复制了pre-commit部分文档,其他详见官方文档。 Git Hooks Like many other…...
nano机器人2:机械臂的视觉抓取
前言 参考链接: 【机械臂入门教程】机械臂视觉抓取从理论到实战 GRCNN 通过神经网络,先进行模型训练,在进行模型评估。 机械臂逆运动学求解 所有串联型6自由度机械臂均是可解的,但这种解通常只能通过数值解法得到,计算难度大&am…...
技术速递|宣布 Java on Azure 开发工具支持 Java on Azure Container Apps
作者:Jialuo Gan 排版:Alan Wang 在 Microsoft Build 2024 期间宣布,Azure Container Apps 现在可为 Java 开发人员提供丰富的操作功能。(详细内容请参见本博客)。 我们很高兴地与大家分享,Azure Toolkit for Intelli…...
随机森林算法实现分类
随机森林算法实现对编码后二进制数据的识别 1.直接先上代码! import numpy as np import pandas as pd from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.ensemble import RandomForestClassifier from sklearn.metrics import …...
Ubuntu卸载软件
在删除这些目录之前,你必须确定一个非常重要的事情:确认没有任何服务正在使用这些版本的 PHP。如果你删除了正在使用的 PHP 版本的扩展目录,那么依赖于这个版本的 PHP 的网站或服务可能会停止工作。 如果你确定某个版本的 PHP 没有在使用中&…...
网络工程师:网络可靠性技术
一、可靠性 平均故障间隔时间MTBF(Mean Time Between Failure)和平均修复时间MTTR(Mean Time to Repair)这两个指标来评价系统的可靠性。 1、平均故障间隔时间MTBF MTBF是指一个系统无故障运行平均时间,通常以小时为单位。MTBF越大可靠性越高。 2、平均修复时间MTTR…...
科技引领未来:高速公路可视化
高速公路可视化监控系统利用实时视频、传感器数据和大数据分析,通过图扑 HT 可视化展示交通流量、车速、事故和路况信息。交通管理人员可以实时监控、快速响应突发事件,并优化交通信号和指挥方案。这一系统不仅提高了道路安全性和车辆通行效率࿰…...
Golang发送POST请求并传递JSON数据
客户端 package mainimport ("c02_get_param/common""fmt""zdpgo_resty" )func main() {// Create a Resty Clientclient : zdpgo_resty.New()// 设置字符串resp, err : client.R().SetHeader("Content-Type", "application/jso…...
C++实现生产者消费者模型
生产者-消费者模型是一种典型的多线程并发模式,常用于在一个共享缓冲区中协调生产者和消费者之间的数据传递。在C中,我们可以使用标准库中的线程、互斥量和条件变量来实现该模型。以下是一个简单的生产者-消费者模型的实现示例: #include &l…...
【Mac】MWeb Pro(好用的markdown编辑器) v4.5.9中文版安装教程
软件介绍 MWeb Pro for Mac是一款Mac上的Markdown编辑器软件,它支持实时预览,语法高亮,自动保存和备份等功能,并且有多种主题和样式可供选择。此外,MWeb还支持多种导出格式,包括HTML、PDF、Word、ePub等&a…...
C++ | Leetcode C++题解之第118题杨辉三角
题目: 题解: class Solution { public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ret(numRows);for (int i 0; i < numRows; i) {ret[i].resize(i 1);ret[i][0] ret[i][i] 1;for (int j 1; j &…...
3D透视图转的时候模型闪动怎么解决?---模大狮模型网
在3D建模与渲染的世界中,透视图是我们观察和操作模型的重要窗口。然而,有时候在旋转透视图时,模型会出现闪动的现象,这不仅影响了我们的工作效率,还可能对最终的渲染效果产生负面影响。本文将探讨这一问题的成因&#…...
如何创建一个vue项目?详细教程,如何创建第一个vue项目?
已经安装node.js在自己找的到的地方新建一个文件夹用于存放项目,记住文件夹的存放路径,以我为例,我的文件夹路径为D:\tydic 打开cmd命令窗口,进入刚刚的新建文件夹 切换硬盘: D: 进入文件夹:cd tydic 使…...
AWS迁移与传输之Migration Hub
AWS Migration Hub是一种集中化的迁移管理服务,可帮助企业规划、跟踪和管理在亚马逊云中进行的各种迁移活动。包括应用程序迁移、数据库迁移、服务器迁移等。 AWS Migration Hub (Migration Hub) 提供一个位置来跟踪使用多个 AWS 工具和合作伙伴解决方案的迁移任务…...
网络渗透思考
1. windows登录的明文密码,存储过程是怎么样的,密文存在哪个文件下,该文件是否可以打开,并且查看到密文 windows的明文密码:是通过LSA(Local Security Authority)进行存储加密的 存储过程:当用户输入密码之…...
2.8万字总结:金融核心系统数据库升级路径与场景实践
OceanBase CEO 杨冰 谈及数字化转型,如果说过去还只是头部金融机构带动效应下的“选择题”。那么现在,我相信数字化转型已经成为不论大、中、小型金融机构的“必答题”。 本文为OceanBase最新发布的《万字总结:金融核心系统数据库升级路径…...
Linux:进程控制(二.详细讲解进程程序替换)
上次讲了:Linux:进程地址空间、进程控制(一.进程创建、进程终止、进程等待) 文章目录 1.进程程序替换1.1概念1.2原理1.3使用一个exec 系列函数execl()函数结论与细节 2.多进程时的程序替换3.其他几个exec系…...
Elasticsearch8.13.4版本的Docker启动关闭HTTPS
博主环境是: 开发环境:SpringbootElasticSearch客户端对应的starter 2.6.3版本 maven配置 <!-- ElasticSearch --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-elas…...
linux 之dma_buf (8)- ION简化版本
一、前言 我们学习了如何使用 alloc_page() 方式来分配内存,但是该驱动只能分配1个PAGE_SIZE。本篇我们将在上一篇的基础上,实现一个简化版的ION驱动,以此来实现任意 size 大小的内存分配。 二、准备 为了和 kernel 标准 ion 驱动兼容&…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
