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

【优选算法篇】：揭开二分查找算法的神秘面纱--数据海洋中的精准定位器

news 来源：原创 2025/7/6 17:45:02

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

在这里插入图片描述

文章目录

一.二分查找算法
二.算法模板
- 模板一
- 模板二
- 模板三
三.例题演练
- 1.x的平方根
- 2.搜索插入位置
- 3.山脉数组的峰值索引
- 4.寻找峰值
- 5.寻找旋转排序数组中的最小值
- 6.点名（0到n-1中缺失的数字）

一.二分查找算法

基本思想

二分查找算法的基本思想是：首先确定目标值可能存在的区间，然后逐步缩小区间直到确定目标值的位置或者确定目标值不存在。这个过程中，每次都会将查找范围缩小一半，因此大大提高了查找效率。
前提条件

有些地方可能对于二分查找算法的前提条件要求必须是有序的待查找数组，如果数组无序则不能使用二分查找。但实际上并不是“必须有序”才能使用，只要待查找数组满足二段性，可以将数组分成两个区间，这两个区间中的子数组又是有序的，同样可以使用二分查找，在后面的一些例题中就有这样的使用。
算法步骤

这里不具体讲解，直接在后面通过模板来讲解
时间复杂度和空间复杂度
- 时间复杂度：二分查找算法的时间复杂度为O(log n)，其中n是数组的长度。因为每次查找都会将范围缩小一半，所以查找的次数是log n(以2为底数的对数)。
- 空间复杂度：因为只使用几个额外的变量（通常是left,right,mid)，所以空间复杂度是O(1)。

二.算法模板

模板一

这里通过一道例题来引出模板一：朴素二分查找

题目：

在这里插入图片描述

算法原理及模板一：
在这里插入图片描述

代码实现：

int search(vector<int>& nums,int target){//朴素二分查找int left = 0, right = nums.size() - 1;int mid = 0;while(left<=right){//获取中间值//两种写法mid = left + (right - left) / 2;//mid = left + (right - left + 1) / 2;if(nums[mid]<target){left = mid + 1;}else if(nums[mid]>target){right = mid - 1;}else{return mid;}}return -1;
}

模板二

这里通过一道例题来引出模板二以及模板三

题目：

在这里插入图片描述

算法原理及模板二：

在这里插入图片描述

模板三

算法原理及模板三：

在这里插入图片描述

代码实现：

vector<int> searchRange(vector<int> &nums, int target)
{// 处理特殊情况，空数组if (nums.empty()){return {-1, -1};}int left = 0, right = nums.size() - 1;int mid = 0;int begin = 0;// 查找区间的左端点// 细节点一：这里只能左指针小于右指针，不能等于while (left < right){// 细节点二：获取中间值这里不能加一mid = left + (right - left) / 2;if (nums[mid] < target){left = mid + 1;}if (nums[mid] >= target){right = mid;}}// 查找左端点结束后，找到继续查找右端点，否则返回没有找到if (left == right && nums[left] == target){begin = left;}else{return {-1, -1};}right = nums.size() - 1;// 查找区间的右端点// 细节点一while (left < right){// 细节点二：获取中间值这里要加一mid = left + (right - left + 1) / 2;if (nums[mid] <= target){left = mid;}if (nums[mid] > target){right = mid - 1;}}return {begin, right};
}

三.例题演练

1.x的平方根

题目：

在这里插入图片描述

算法原理：

从1到x的数组中：[0，x-1]（【1，2，3…x】），因为返回的是整数，对于小数部分要舍去，因此要往小的数进位，比如2.82842，进位到2而不是3，所以根据二段性可以分为两个区间：假设目标值下标为s，[0，s]区间中的值的平方都小于等于x，（s，x-1]区间中的值的平方都大于x，使用模板三。

代码实现：

int mySqrt(int x) {if(x<1){return 0;}int left=1,right=x;long long mid=0;while(left<right){mid=left+(right-left+1)/2;if(mid*mid<=x){left=mid;}else{right=mid-1;}}return left;
}

2.搜索插入位置

题目：

在这里插入图片描述

算法原理：

因为可能存在目标值不存在的情况，所以不能使用朴素二分查找模板，这里只能使用模板二或者模板三，这里以模板三为例。

根据二段性可以将数组分为两个区间，假设目标值下标为s，[0，s]区间的值小于等与目标值，(s，n-1)区间的值大于目标值。

当出现目标值不存在的情况时，找到的一定是小于目标值的下标位置，直接返回该位置的下一个即可。

代码实现：

int searchInsert(vector<int>& nums,int target){int left=0,right=nums.size()-1;int mid;while(left<right){mid = left + (right - left + 1) / 2;if(nums[mid]<=target){left = mid;}else{right = mid - 1;}}if(nums[left]<target){return left+1;}return left;
}

3.山脉数组的峰值索引

题目：

在这里插入图片描述

算法原理：

在这道题中，如果第一眼看数组不是有序的，可能就会觉得不能使用二分查找算法来解，但是，我们仔细观察可以发现，在这道题中，根据题目要求可以将数组分成两端，也就使数组具有二段性，因此这道题实际上还是使用二分查找算法来解。

假设峰值是s，s左边的值[0，s)全都有序，也就是升序排列，前一个值小于后一个值，而s右边的值(s，n-1]也全都有序，但是是降序排列，前一个值大于后一个值。

根据二段性就可以使用模板，这里用模板三来演示。

代码实现：

int peakIndexInMountainArray(vector<int>& arr){int left = 0, right = arr.size() - 1;int mid = 0;while(left<right){mid = left + (right - left + 1) / 2;if(arr[mid-1]<arr[mid]){left = mid;}else{right = mid - 1;}}return left;
}

4.寻找峰值

题目：

在这里插入图片描述

算法原理：

这道题和上面的山脉数组的峰值算法原理一样，同样可以使用相同的模板来解。唯一不同的是，这道题中的数组可能有多个峰值，但我们只需找到一个返回即可。

代码实现：

int findPeakElement(vector<int>& nums){int left = 0, right = nums.size() - 1;int mid=0;while(left<right){mid = left + (right - left + 1) / 2;if(nums[mid-1]<nums[mid]){left = mid;}else{right = mid - 1;}}return left;
}

5.寻找旋转排序数组中的最小值

题目：

在这里插入图片描述

算法原理：
在这道题中，给定的数组同样不满足有序的条件，但是根据题意可以发现，数组满足二段性。

假设最小值下标为s，最大值左边区间的值[0,s)，全都小于最大值；最小值右边区间的值[s，n-1]全都小于数组第一个值（下标为0)；因为数组第一个值在左边区间中是最小的，左边区间的值又全都大于右边区间的最后一个值（下标为n-1)，也就是数组最后一个值。

根据二段性可以使用模板二或者模板三，使用不同的模板时，要处理不同的细节。

使用模板二，就是以最后一个元素作为区分值，最小值左边元素都大于最后一个元素，最小值右边都小于等于最后一个元素，直接找最小值。

使用模板三，就是以第一个元素为区分值，最小值元素左边都大于等于第一个元素，最小值右边都小于第一个元素，找最大值，最小值就是最大值后一个，因此循环结束后，还要将下标再加一才是最小值的下标。

代码实现：

int findMin(vector<int>& nums){int left = 0, right = nums.size() - 1;//利用二段性,以最后一个元素为区分值//最小值左边元素都大于最后一个元素，最小值右边都小于等于最后一个元素//直接找最小值while(left<right){int mid = left + (right - left) / 2;if(nums[mid]>nums[nums.size()-1]){left = mid + 1;}else{right = mid;}}//以第一个元素为区分值//最小值元素左边都大于等于第一个元素，最小值右边都小于第一个元素//找最大值，最小值就是最大值后一个while(left<right){int mid = left + (right - left + 1) / 2;if(nums[mid]>=nums[0]){left = mid;}else{right = mid - 1;}}if(left!=nums.size()-1){left++;}return nums[left];
}

6.点名（0到n-1中缺失的数字）

题目：

在这里插入图片描述

算法原理：
这道题相当于从0当n-1中，查找缺失的数字，仔细看我们可能看不出来有什么二段性质，但是如果我们将每个值都和下标对比，就是发现二段性。

这里以缺失数字4的数组为例：

【0，1，2，3，5，6】

下标：【0，1，2，3，4，5】

从上面我们可以看出，缺失数字的下标左边区间的下标对应数组中的数字，而缺失数字右边区间的下标则是对应数字减一。

根据上面的二段性就可以使用模板二。

注意还有一种情况可能是：【0，1，2，3】数组有序，这时缺失的数字就是4，因此在循环结束后，要进行一个判断，如果当前下标是最后一个，且下标对应数组中的数字，这时下标要加一返回。

代码实现：

int takeAttendance(vector<int>& nums){int left = 0, right = nums.size() - 1;while(left<right){int mid = left + (right - left) / 2;if(nums[mid]==mid){left = mid + 1;}else{right = mid;}}if(left==nums.size()&&nums[left]==left){left++;}return left;
}

以上就是关于二分查找算法以及例题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
在这里插入图片描述

【优选算法篇】：揭开二分查找算法的神秘面纱--数据海洋中的精准定位器

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨ ✨ 个人主页：余辉zmh–CSDN博客 ✨ 文章所属专栏：c篇–CSDN博客文章目录一.二分查找算法二.算法模板模板一模板二模板三三.例题演练1.x的平…...

编程日记 2025/7/6 17:45:02

【机器学习算法】——数据可视化

1. 饼图：显示基本比例关系 import matplotlib.pyplot as pltplt.rcParams[font.sans-serif] [SimHei] plt.rcParams[axes.unicode_minus] False# ——————————————————————————————————————————————————————…...

编程日记 2025/7/5 13:13:56

比特币与区块链原理解析：矿机挖矿与去中心化的未来

✨✨ 欢迎大家来访Srlua的博文（づ￣3￣）づ╭❤～✨✨ 🌟🌟 欢迎各位亲爱的读者，感谢你们抽出宝贵的时间来阅读我的文章。我是Srlua小谢，在这里我会分享我的知识和经验。&am…...

编程日记 2025/6/29 23:34:40

SpringBoot教程（十四） SpringBoot之集成Redis

SpringBoot教程（十四） | SpringBoot之集成Redis 一、Redis集成简介二、集成步骤 2.1 添加依赖2.2 添加配置2.3 项目中使用之简单使用 （举例讲解）2.4 项目中使用之工具类封装 （正式用这个）2.5 序列化 &…...

编程日记 2025/7/1 11:51:22

Qt之第三方库QCustomPlot使用（二）

Qt开发系列文章 - qcustomplot（二） 目录前言一、Qt开源库二、QCustomPlot 1.qcustomplot介绍 2.qcustomplot下载 3.qcustomplot移植 4.修改项目文件.pro 5.提升QWidget类‌ 三、技巧讲解 1.拖动缩放功能 2.等待更新总结前言 Qt第三方…...

编程日记 2025/7/2 17:26:54

机器学习决策树原理详解

一、引言在当今蓬勃发展的人工智能与大数据领域，大模型正以前所未有的影响力改变着众多行业的格局。而决策树作为机器学习算法家族中的经典成员，以其简洁直观的特点和广泛的适用性，不仅能独立解决诸多实际问题，更是诸多先进大模…...

编程日记 2025/6/30 12:18:49

深入探索JavaScript循环语句：从基础到高级应用

深入探索JavaScript循环语句：从基础到高级应用在前端开发中，JavaScript 的循环语句是构建动态和交互式网页的关键工具。本文将全面介绍 JavaScript 中的几种主要循环语句，包括 for、while、do...while 以及 for...in 和 for...of&#xff0…...

编程日记 2025/7/6 12:55:16

从0开始深度学习（35）——YOLO V5原理详解

以YOLO V5s为例，介绍YOLO V5的网络结构，以及其中具体的功能模块 1 YOLO V5的整体网络结构 YOLO V5网络结构分为四个部分： 输入端： 输入端负责对输入图像进行预处理，包括数据增强、锚框计算等。骨干网络（Ba…...

编程日记 2025/7/2 21:19:53

高级数据库模式设计与性能优化

数据库模式设计不仅仅是创建表和字段那么简单，还需要考虑数据的一致性、性能优化、安全性和可扩展性等多个方面。本文将深入探讨数据库模式设计的高级技巧，并提供一个实际的例子来展示如何在项目中应用这些技巧。 1. 数据库模式设计的高级技巧 1.1 多对…...

编程日记 2025/7/6 17:35:54

【开源免费】基于SpringBoot+Vue.JS图书进销存管理系统（JAVA毕业设计）

博主说明：本文项目编号 T 082 ，文末自助获取源码 \color{red}{T082，文末自助获取源码} T082，文末自助获取源码目录一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…...

编程日记 2025/7/6 16:10:11

监控易助力扩容1000个点位

铁路交通作为城市发展的重要动脉，其IT系统的稳定运行对于保障铁路运输的安全与高效至关重要。近期，四川某铁路用户为了进一步提升IT基础资源的监控和管理水平，决定对现有的运维体系进行扩容升级，引入了监控易一体化运维软件&#…...

编程日记 2025/7/5 12:39:28

克服大规模语言模型限制，构建新的应用方法——LangChain

大模型大模型的出现和落地开启了人工智能(AI)新一轮的信息技术革命，改变了人们的生活方式、工作方式和思维方式。大模型的落地需要数据、算力和算法三大要素。经过几年发展，大模型的数据集(包括多模态数据集)制作已经形成了规约，Meta、Go…...

编程日记 2025/7/6 17:28:50

1.安装开发工具 cmake brew install cmakeopenocd brew install openocdarm-none-eabi-gcc 用 brew 安装的版本会出现如下错误： arm-none-eabi-gcc: fatal error: cannot read spec file nosys.specs: No such file or directory用 arm 官方的版本没有问题。 cd …...

编程日记 2025/7/4 6:52:30

Leetcode 每日一题 1.两数之和

目录问题描述示例示例 1 示例 2 示例 3 提示解决方案算法思路过题图片代码实现复杂度分析注意事项题目链接结论问题描述给定一个整数数组 nums 和一个目标值 target，请你找出数组中和为目标值的那两个整数，并返回它们的数组下…...

编程日记 2025/7/2 1:23:54

柯桥职场商务英语生活英语口语培训外贸纺织口语学习

"等一下"该怎么说？ 大家应该都知道，wait a moment是一个祈使句，祈使句就难免带有命令的口吻，还有点不耐烦。如果你把“等一下”说成wait a moment，外国人多半认为你是个傲慢无礼的人。毕竟在他们看来wait a…...

编程日记 2025/7/4 22:33:20

ElasticSearch如何做性能优化？

大家好，我是锋哥。今天分享关于【ElasticSearch如何做性能优化？】面试题。希望对大家有帮助； ElasticSearch如何做性能优化？ 1000道互联网大厂Java工程师精选面试题-Java资源分享网在 Elasticsearch 中，性能优化是…...

编程日记 2025/7/1 17:13:18

深度学习常用损失函数介绍

均方差损失（Mean Square Error，MSE） 均方误差损失又称为二次损失、L2损失，常用于回归预测任务中。均方误差函数通过计算预测值和实际值之间距离（即误差）的平方来衡量模型优劣。即预测值和真实值越接近&…...

编程日记 2025/7/3 12:08:38

PSHuman 部署笔记

目录 github地址： 依赖项： xformers安装： 解决方法，安装xformers smpl_data下载： 推理步骤： SMPLDataset 香港科技大学提出了一种叫PSHuman的新框架。这个方法利用了一个多视角扩散模型的“先验知识…...

编程日记 2025/7/4 19:12:41

怎么样能使Ubuntu的文件浏览器显示当前目录的路径，而不是只显示一个文件名？

默认情况下Ubuntu的文件浏览器是只显示当前目录的目录名的，这很不便我们查看路径或直接利用路径进行定位，那么怎么样能使Ubuntu的文件浏览器显示当前目录的路径呢？ 两种方法： 第1种-临时方法按下快捷键 Ctrl L，导航…...

编程日记 2025/7/4 15:29:26

自回归模型（AR ）

最近看到一些模型使用了自回归方法，这里就学习一下整理一下相关内容方便以后查阅。自回归模型（AR ） 自回归模型（AR ）AR 模型的引入AR 模型的定义参数的估计方法模型阶数选择平稳性与因果性条件自相关与偏自相关函数优…...

编程日记 2025/7/5 19:46:06

工具推荐-js爬取工具

现在测试方向都偏向于从js中的接口来入手找到可以进的点，关于快速扫描js文件来发现敏感接口的工具有很多，下面的jjjjs就是其一项目地址: GitHub - ttstormxx/jjjjjjjjjjjjjs: 爬网站JS文件，自动fuzz api接口，指定api接口&#x…...

编程日记 2025/7/4 23:10:56

CSS学习记录05

CSS外边距 CSS margin属性用于在任何定义的边框之外，为元素周围创建空间。通过CSS，您可以完全控制外边距，一些属性可用于设置元素每侧（上、右、下和左）的外边距。 Margin - 单独的边 CSS拥有用于为元素的每一侧指定…...

编程日记 2025/7/4 16:09:56

差异基因富集分析（R语言——GOKEGGGSEA）

接着上次的内容，上篇内容给大家分享了基因表达量怎么做分组差异分析，从而获得差异基因集，想了解的可以去看一下，这篇主要给大家分享一下得到显著差异基因集后怎么做一下通路富集。 1.准备差异基因集我就直接把上次分享的拿到这…...

编程日记 2025/6/30 16:25:18

ISO 45001 职业健康安全管理体系的实施具有多方面的重要意义

对企业的意义提升企业形象：实施 ISO 45001 体系体现了企业对员工职业健康安全的重视和承诺，有助于树立良好的企业形象，增强企业在社会公众、客户、投资者等方面的认可度和美誉度，提升企业的市场竞争力。增强员工满意度和忠诚度&a…...

编程日记 2025/7/4 15:38:53

HarmonyOS-中级(三)

文章目录合理使用动画和转场Web组件和WebView给应用添加通知和提醒 🏡作者主页：点击！ 🤖HarmonyOS专栏：点击！ ⏰️创作时间：2024年12月08日12点12分合理使用动画和转场动效场景设计&#x…...

编程日记 2025/7/5 6:30:20

报错:Invalid HTTP method: PATCH executing PATCH http://XXX.XXX

分析： 问题在于我使用feignclietn调用PatchMapping方法时，发送的 PATCH 请求方法出现了不匹配的情况。虽然说springboot自带了RESTful风格的方法（GET、POST、PUT、DELETE、PATCH，但是PATCH相较于前几个来说算是新的HTTP方法&#…...

编程日记 2025/7/2 0:08:33

Open WebUI项目源码学习记录（从0开始基于纯CPU环境部署一个网页Chat服务）

感谢您点开这篇文章:D，鼠鼠我是一个代码小白，下文是学习开源项目Open WebUI过程中的一点笔记记录，希望能帮助到你～ 本人菜鸟，持续成长，能力不足有疏漏的地方欢迎一起探讨指正，比心心&#xff5e…...

编程日记 2025/7/1 19:14:57

WPF Prism 01-BootstrapperShell

Prism介绍 Prism 是一个用于在 WPF、.NET MAUI、Uno 平台和 Xamarin Forms 中构建松耦合、可维护和可测试的 XAML 应用程序的框架。每个平台都有单独的发布版本，并且这些版本将在独立的开发时间线上进行开发。Prism 提供了一组设计模式的实现，这些模式有…...

编程日记 2025/7/2 13:07:11

在Ubuntu22.04 jammy下用qemu模型riscv32环境装鸿蒙（未完成，待续）

在使用实体ESP32C3 安装鸿蒙失败后，就是这个：完全按照手册win10里装Ubuntu 虚拟机然后编译ESP32（主要是想针对ESP32C3和S3）开发板的鸿蒙系统(失败)-CSDN博客转向用qemu模拟环境装鸿蒙学习手册riscv32_virt/README_zh.md OpenHar…...

编程日记 2025/6/30 20:53:16

第2章：CSS基本语法 --[CSS零基础入门]

CSS（层叠样式表，Cascading Style Sheets）是用来描述HTML或XML（包括各种XML：SVG, MathML 或 XHTML）等文档的外观和格式的语言。以下是CSS的基本语法： 1.选择器 1.元素选择器元素选择器是基于HTML标签名称来选择元素的。当你使用元素选择器时，你是在告诉浏览器对页面…...

编程日记 2025/6/30 1:42:09

win11 恢复任务栏copilot图标, 亲测有效

1、修改C:\Windows\System32\IntegratedServicesRegionPolicySet.json，解除中国不能使用copilot的限制。使用Notepad搜索copilot全文搜索，将下面两处的“CN,”删除，删除后如下： {"$comment": "Show Copilot on t…...

编程日记 2025/7/6 5:10:12

Python爬虫实战：抓取拼多多商品详情数据（基于pdd.item_get接口）

在当前的电商市场中，拼多多以其独特的拼团模式和优惠价格吸引了大量用户，成为继淘宝、京东之后的又一大电商平台。对于数据分析和市场研究者来说，获取拼多多的商品详情数据显得尤为重要。本文将介绍如何使用Python爬虫技术，通过调…...

编程日记 2025/6/29 18:34:31

如何在x86模拟器和鸿蒙API9如何使用MQTT模块ohos_mqtt

目录引言安装失败的原因如何编译so文件的x86_64版本下载源代码安装NDK 代码编译安装MQTT软件包避免MQTT软件包自动升级设置libs 客户端程序的编写运行测试结语参考文献引言在上周的博客（如何在鸿蒙API9和x86模拟器中使用MQTT-CSDN博客&am…...

编程日记 2025/7/3 7:31:50

VB.NET 从入门到精通：开启编程进阶之路

摘要： 本文全面深入地阐述了 VB.NET 的学习路径，从基础的环境搭建与语法入门开始，逐步深入到面向对象编程、图形用户界面设计、数据访问、异常处理、多线程编程以及与其他技术的集成等核心领域，通过详细的代码示例与理论讲解&…...

编程日记 2025/7/1 10:10:52

芝法酱学习笔记（1.3）——SpringBoot+mybatis plus+atomikos实现多数据源事务

一、前言 1.1 业务需求之前我们在讲解注册和登录的时候，有一个重要的技术点忽略了过去。那就是多数据源的事务问题。按照我们的业务需求，monitor服务可能涉及同时对监控中心数据库和企业中心数据库进行操作，而我们希望这样的操作在一个事…...

编程日记 2025/7/1 23:29:36

图像处理插件：让小程序焕发视觉新生的秘密武器

在小程序开发中，图像处理是一个重要的环节，它涉及到图片的加载、显示、裁剪、压缩等多个方面。为了简化这一复杂过程，开发者通常会使用图像处理插件。这些插件不仅提供了丰富的图像处理功能，还封装了底层的图像操作逻辑&#xff0…...

编程日记 2025/7/1 16:45:25

力扣刷题TOP101: 27.BM34 判断是不是二叉搜索树

目录： 目的思路复杂度记忆秘诀 python代码目的： 给定一个二叉树根节点，请判断这棵树是不是二叉搜索树。二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。思路什么是二叉搜索树&am…...

编程日记 2025/7/3 22:15:15

Linux图形化工具推荐

1、MobaXterm MobaXterm Xserver with SSH, telnet, RDP, VNC and X11 - DownloadFree X server for Windows with tabbed SSH terminal, telnet, RDP, VNC and X11-forwarding - Downloadhttps://mobaxterm.mobatek.net/download.html 2、FinalShell FinalShell SSH工具,服…...

编程日记 2025/7/3 5:17:53

文章目录

一.二分查找算法

二.算法模板

模板一

模板二

模板三

三.例题演练

1.x的平方根

2.搜索插入位置

3.山脉数组的峰值索引

4.寻找峰值

5.寻找旋转排序数组中的最小值

6.点名（0到n-1中缺失的数字）

相关文章：