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

二分法篇——于上下边界的扭转压缩间,窥见正解辉映之光(1)

在这里插入图片描述

前言

二分法,这一看似简单却又充满哲理的算法,犹如一道精巧的数学之门,带领我们在问题的迷雾中找到清晰的道路。它的名字虽简单,却深藏着智慧的光辉。在科学的浩瀚星空中,二分法如一颗璀璨的星辰,指引着我们如何高效地寻找答案。本文将带领大家走进二分法的世界,探讨它的原理、应用及其在各种问题中的深远影响。

一. 原理讲解

二分法,顾名思义,是将一个问题或区间不断地分成两个部分,逐步逼近目标答案。最常见的应用是求解有序数列中的某个元素,或者求解某个函数的零点。
其基本思路如下:

  • 初始化区间: 在一维空间中,选择一个包含目标值的初始区间。
  • 逐步缩小区间: 将区间分为两半,判断目标值是否在左半区间或右半区间中,根据判断结果进一步缩小搜索区间。
  • 终止条件: 直到找到目标值或区间缩小到足够小为止。

这种“分而治之”的策略,极大地提高了搜索效率,尤其在处理大规模数据时,具有显著的优势。

下面我们将结合具体题型进行二分法的使用与讲解。

二. 二分查找

2.1 题目链接:https://leetcode.cn/problems/binary-search/description/

2.2 题目分析:

  1. 题目中给出一个升序排列的数组,其中元素有正有负
  2. 要求查找并返回数组内与target相同的元素的下标
  3. 如果不存在,则返回-1
  4. nums内的所有元素都不重复

2.3 思路讲解

暴力解法:

此题较为简单,查找目标值,直接遍历即可,且数据量不大,应该不会超时,不再给出示例代码。

二分法:

  1. 根据上文提到的原理可知,我们首先需要确定左右边界,因此令left=0,right=nums.size()-1.
  2. 由于该题数组为升序排列,二分之后具有二段性,即mid左侧区间内所有元素都小于mid,而mid右侧区间内所有元素都大于mid
  3. 因此我们进行while循环,逐次二分判断即可。如果循环期间内未成功返回target的下标,说明不存在,反之,返回mid即可。

代码实现:

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;//确定左右边界//由于两个指针相交时还未判断是否等于target,因此需要取等号while(left<=right){int mid=(left+right)/2;if(nums[mid]>target){right=mid-1;}//更新右边界else if(nums[mid]<target){left=mid+1;}//更新左区间else{return mid;}}return -1;}
};

三. 在排序数组中查找元素的第一个和最后一个位置

3.1 题目链接:https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

3.2 题目分析:

  1. 题目给出按照升序排列的数组nums以及目标值target,要求返回target在数组内的起始下标和结束下标。
  2. 如果不存在,则返回{-1,-1}
  3. 时间复杂度要求为logn。

3.3 思路讲解:

问题:时间复杂度的要求和数组的二段性已经很明显的提示我们需要使用二分法,可是二分法我们只尝试过查找单个target,面对一连串的target,我们又该如何处理呢?

虽然我们要查找的target是一串区间,但是数组仍满足二段性,在target起始区间的左侧,所有元素均小于target,而在target结束区间的右侧,所有元素均大于target。

因此,我们使用两次二分,分别查找该区间的左右边界即可,具体步骤如下:

  • 仍旧令left=0,right=nums.size()-1,确定左右区间进行二分查找

  • 查找target的起始下标(左边界)如图:

  • 在这里插入图片描述

  • 查找target的结束下标(右边界)如图:

  • 在这里插入图片描述

代码实现:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0){return {-1,-1};}int left=0,right=nums.size()-1;int begin=0;//查找左边界while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}//更新leftelse{right=mid;}//更新right}if(nums[left]!=target){return {-1,-1};}//若左边界未查找成功,说明不存在target,直接返回begin=left;//查找成功,更新左边界//查找右边界right=nums.size()-1;//将right恢复为初始状态while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]==target){left=mid;}//更新leftelse{right=mid-1;}//更新right}return {begin,right};}
};

四. x的平方根

4.1 题目链接:https://leetcode.cn/problems/sqrtx/description/

4.2 题目分析:

  • 给出x,要求计算x的算术平方根
  • 结果只保留整数部分,而非按照四舍五入规则
  • x的范围很大,使用int会存在越界情况
  • x可能为0,此时应特殊处理

4.3 思路讲解:

我们可假设目标值为target,那么该题所有答案都在[0,n]的这个数组内。

且[0,target]内,所有元素的平方和均小于x,[target,x]内,所有元素的平方和均大于x,即满足二段性,因此可考虑使用二分法进行解决。
具体步骤如下:

  1. 令left=1,right=x,确实左右区间进行遍历
  2. 进行取中点操作,mid=left+(right-left+1)/2,如果mid*mid>x,说明target在[left,mid]内,right更新为mid-1.
  3. 如果mid*mid<=x,说明target在[left,mid]内,left更新为mid。
  4. 进行循环遍历,最终left即为所求。

4.4 代码实现:

class Solution {
public:int mySqrt(int x) {int left=1,right=x;if(x==0){return 0;}while(left<right){long long mid=left+(right-left+1)/2;//防止越界if(mid*mid<=x){left=mid;}//更新leftelse{right=mid-1;}//更新right}return left;}
};

五. 山脉数组的峰顶索引

5.1 题目链接:https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

5.2 题目分析:

  • 该数组呈山脉分布,设峰值元素为target,则[0,target]内元素递增,[target,n-1]内元素递减,要求返回峰值元素的下标
  • 时间复杂度要求为logn

5.3 思路讲解:

由上述分析不难发现可是用二分法。

  1. 令left=1,right=nums.size()-2,作为左右边界。
    注意:此处如此初始化是因为至少需要3个元素才能组成一个山峰,因此下标为0和下标为n-1的元素不可能为峰顶元素
  2. 求取中点mid=left+(right-left+1)/2,并令nums[mid]与nums[mid-1]进行比较。
  • 如果nums[mid]>=nums[mid-1],说明mid处在上升区间内,target一定位于[mid,right]内,因此更新left为mid
  • 如果nums[mid]<nums[mid-1],说明mid处在下降区间内,target一定位于[left,mid]内,因此更新right为mid-1
  1. while循环二分操作,最后left即为所求target

5.4 代码实现:

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left=1,right=arr.size()-2;//峰顶元素即为最大值while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}//mid在上升区间内else {right=mid-1;}}return left;}
};

六. 小结

6.1 局限性

尽管二分法在许多情况下都表现出极高的效率,但它也并非万能。在应用二分法时,要求数据必须是有序的,否则无法直接应用。此外,二分法在处理某些特殊类型的问题时,可能需要额外的技巧或调整。例如,求解无序数据中的元素时,二分法并不能直接使用,需要先进行排序或采取其他的算法。

6.2 时间复杂度

二分法的时间复杂度为 O(log n),这使得它在处理大规模数据时,具有非常高的效率。在最坏的情况下,每一步都将问题规模缩小一半,从而大大减少了运算的次数。与线性搜索相比,二分法能大幅度提高搜索效率,尤其是在数据量极大的情况下。

6.3 结语

二分法作为一种简单而高效的算法,已经成为计算机科学与数学中不可或缺的一部分。它不仅仅是一个算法工具,更是我们思考问题、解决问题的哲学。在这条“二分之间”的道路上,我们不仅找到了问题的解答,也探索到了求解问题的一种智慧。它教会我们,在复杂问题面前,不妨将问题拆解,逐步攻克,最终发现通往答案的光明之路。

本篇关于二分法的介绍就暂告一段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!
在这里插入图片描述

相关文章:

二分法篇——于上下边界的扭转压缩间,窥见正解辉映之光(1)

前言 二分法&#xff0c;这一看似简单却又充满哲理的算法&#xff0c;犹如一道精巧的数学之门&#xff0c;带领我们在问题的迷雾中找到清晰的道路。它的名字虽简单&#xff0c;却深藏着智慧的光辉。在科学的浩瀚星空中&#xff0c;二分法如一颗璀璨的星辰&#xff0c;指引着我们…...

# 01_Python基础到实战一飞冲天(三)--python面向对象(一)--简单类

01_Python基础到实战一飞冲天&#xff08;三&#xff09;–python面向对象&#xff08;一&#xff09;–简单类 一、面向对象-01-基本概念 1、面向对象(OOP) 面向对象编程 —— Object Oriented Programming 简写 OOP。 2、面向对象(OOP) 学习目标 了解 面向对象 基本概念…...

sentinel使用手册

1.引入依赖 <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-sentinel</artifactId></dependency>2.yaml spring:cloud:sentinel:transport:dashboard: localhost:8090 #sentinel控制台地址…...

搜索二维矩阵 II(java)

题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 代码思路&#xff1a; 用暴力算法&#xff1a; class Solution {public boolean searchMatrix(…...

Python语法基础(四)

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 高阶函数之map 高阶函数就是说&#xff0c;A函数作为B函数的参数&#xff0c;B函数就是高阶函数 map&#xff1a;映射 map(func,iterable) 这个是map的基本语法&#xff0c;…...

03_Django视图

三、Django模板 模板Templates 在Django框架中&#xff0c;模板是可以帮助开发者快速生成呈现给用户页面的工具 模板的设计方式实现了我们MVT中VT的解耦(M:Model&#xff0c;V:View&#xff0c;T:Template)&#xff0c;VT有着N:M的关系&#xff0c;一个V可以调用任意T&#xf…...

如何从 Hugging Face 数据集中随机采样数据并保存为新的 Arrow 文件

如何从 Hugging Face 数据集中随机采样数据并保存为新的 Arrow 文件 在使用 Hugging Face 的数据集进行模型训练时&#xff0c;有时我们并不需要整个数据集&#xff0c;尤其是当数据集非常大时。为了节省存储空间和提高训练效率&#xff0c;我们可以从数据集中随机采样一部分数…...

11 设计模式之代理模式(送资料案例)

一、什么是代理模式&#xff1f; 在现实生活中&#xff0c;我们常常遇到这样的场景&#xff1a;由于某些原因&#xff0c;我们可能无法亲自完成某个任务&#xff0c;便会委托他人代为执行。在设计模式中&#xff0c;代理模式 就是用来解决这种“委托”问题的&#xff0…...

MongoDB聚合操作

1.聚合操作 聚合操作处理数据记录并返回计算结果。聚合操作组值来自多个文档&#xff0c;可以对分组数据执行各种操作以返回单个结果。聚合操作包含三类&#xff1a;单一作用聚合、聚合管道、MapReduce。 单一作用聚合&#xff1a;提供了对常见聚合过程的简单访问&#xff0c…...

第二十三周周报:High-fidelity Person-centric Subject-to-Image Synthesis

目录 摘要 Abstract TDM SDM SNF 测试时的人物细节捕捉 主要贡献 总结 摘要 本周阅读了一篇2024年CVPR的关于高保真度、以人物为中心的图像合成方法的论文&#xff1a;High-fidelity Person-centric Subject-to-Image Synthesis。该论文提出了一种名为Face-diffuser的…...

Cesium 与 Leaflet:地理信息可视化技术比较

在现代地理信息系统(GIS)和空间数据可视化领域,Cesium 和 Leaflet 是两种非常常见的地理可视化库,它们各自适用于不同的应用场景。Cesium 专注于三维地球视图和复杂空间分析,而 Leaflet 则注重轻量级的二维地图展示。本文将对这两种技术进行详细的对比,帮助开发者根据具体…...

Linux 服务器使用指南:诞生与演进以及版本(一)

一、引言 在当今信息技术的浪潮中&#xff0c;Linux 操作系统无疑是一个关键的支柱&#x1f60e;。无论是在服务器管理、软件开发还是大数据处理领域&#xff0c;Linux 都以其卓越的适应性和优势脱颖而出&#x1f44d;。然而&#xff0c;对于许多新手而言&#xff0c;Linux 系统…...

龙蜥 Linux 安装 JDK

龙蜥 Linux 安装 JDK 下载安装解压到目标路径设置环境变量直接在启动脚本中临时设置 参考资料 下载 这个就不赘述了&#xff0c;参考资料中的另外两篇安装帖&#xff0c;都有。 如果不能上网&#xff0c;也可以去内网其他之前装过JDK的服务器&#xff0c;直接复制过来。 tar …...

Python小白语法基础20(模块与包)

0) 参考文章 python的模块(module)、包(package)及pip_python package-CSDN博客Python之函数、模块、包库_python函数、模块和包-CSDN博客Python函数模块自定义封装及模块嵌套导入&#xff08;手把手教程&#xff09;_python如何封装一个模块-CSDN博客 1) 模块与包说明 软件…...

详解 Qt QtPDF之QPdfPageNavigator 页面跳转

文章目录 前言头文件&#xff1a; 自 Qt 6.4 起继承自&#xff1a; 属性backAvailable : const boolcurrentLocation : const QPointFcurrentPage : const intcurrentZoom : const qrealforwardAvailable : const bool 公共函数QPdfPageNavigator(QObject *parent)virtual ~QPd…...

通俗易懂:序列标注与命名实体识别(NER)概述及标注方法解析

目录 一、序列标注&#xff08;Sequence Tagging&#xff09;二、命名实体识别&#xff08;Named Entity Recognition&#xff0c;NER&#xff09;**命名实体识别的作用****命名实体识别的常见实体类别** &#xff1a; 三、标签类型四、序列标注的三种常见方法1. **BIO&#xf…...

【C语言】二叉树(BinaryTree)的创建、3种递归遍历、3种非递归遍历、结点度的实现

代码主要实现了以下功能&#xff1a; 二叉树相关数据结构定义 定义了二叉树节点结构体 BiTNode&#xff0c;包含节点数据值&#xff08;字符类型&#xff09;以及指向左右子树的指针。 定义了顺序栈结构体 SqStack&#xff0c;用于存储二叉树节点指针&#xff0c;实现非递归遍历…...

2024年11月文章一览

2024年11月编程人总共更新了21篇文章&#xff1a; 1.2024年10月文章一览 2.《使用Gin框架构建分布式应用》阅读笔记&#xff1a;p307-p392 3.《使用Gin框架构建分布式应用》阅读笔记&#xff1a;p393-p437 4.《使用Gin框架构建分布式应用》读后感 5.《Django 5 By Example…...

重生之我在异世界学编程之C语言:二维数组篇

大家好&#xff0c;这里是小编的博客频道 小编的博客&#xff1a;就爱学编程 很高兴在CSDN这个大家庭与大家相识&#xff0c;希望能在这里与大家共同进步&#xff0c;共同收获更好的自己&#xff01;&#xff01;&#xff01; 本文目录 引言正文一 二维数组的创建1. 二维数组的…...

和鲸科技创始人CEO范向伟出席首届工业智算产业发展研讨会,共话 AI 创新与产业化落地

11 月 22 日&#xff0c;首届工业智算产业发展研讨会在中国工业互联网研究院召开。工业和信息化部党组成员、副部长单忠德&#xff0c;国家信息中心大数据发展部副主任魏颖出席会议并致辞。中国工程院院士、北京化工大学教授高金吉&#xff0c;工业和信息化部信息通信发展司二级…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...