二分法篇——于上下边界的扭转压缩间,窥见正解辉映之光(1)
前言
二分法,这一看似简单却又充满哲理的算法,犹如一道精巧的数学之门,带领我们在问题的迷雾中找到清晰的道路。它的名字虽简单,却深藏着智慧的光辉。在科学的浩瀚星空中,二分法如一颗璀璨的星辰,指引着我们如何高效地寻找答案。本文将带领大家走进二分法的世界,探讨它的原理、应用及其在各种问题中的深远影响。
一. 原理讲解
二分法,顾名思义,是将一个问题或区间不断地分成两个部分,逐步逼近目标答案。最常见的应用是求解有序数列中的某个元素,或者求解某个函数的零点。
其基本思路如下:
- 初始化区间: 在一维空间中,选择一个包含目标值的初始区间。
- 逐步缩小区间: 将区间分为两半,判断目标值是否在左半区间或右半区间中,根据判断结果进一步缩小搜索区间。
- 终止条件: 直到找到目标值或区间缩小到足够小为止。
这种“分而治之”的策略,极大地提高了搜索效率,尤其在处理大规模数据时,具有显著的优势。
下面我们将结合具体题型进行二分法的使用与讲解。
二. 二分查找
2.1 题目链接:https://leetcode.cn/problems/binary-search/description/
2.2 题目分析:
- 题目中给出一个升序排列的数组,其中元素有正有负
- 要求查找并返回数组内与target相同的元素的下标
- 如果不存在,则返回-1
- nums内的所有元素都不重复
2.3 思路讲解
暴力解法:
此题较为简单,查找目标值,直接遍历即可,且数据量不大,应该不会超时,不再给出示例代码。
二分法:
- 根据上文提到的原理可知,我们首先需要确定左右边界,因此令left=0,right=nums.size()-1.
- 由于该题数组为升序排列,二分之后具有二段性,即mid左侧区间内所有元素都小于mid,而mid右侧区间内所有元素都大于mid
- 因此我们进行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 题目分析:
- 题目给出按照升序排列的数组nums以及目标值target,要求返回target在数组内的起始下标和结束下标。
- 如果不存在,则返回{-1,-1}
- 时间复杂度要求为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,即满足二段性,因此可考虑使用二分法进行解决。
具体步骤如下:
- 令left=1,right=x,确实左右区间进行遍历
- 进行取中点操作,mid=left+(right-left+1)/2,如果mid*mid>x,说明target在[left,mid]内,right更新为mid-1.
- 如果mid*mid<=x,说明target在[left,mid]内,left更新为mid。
- 进行循环遍历,最终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 思路讲解:
由上述分析不难发现可是用二分法。
- 令left=1,right=nums.size()-2,作为左右边界。
注意:此处如此初始化是因为至少需要3个元素才能组成一个山峰,因此下标为0和下标为n-1的元素不可能为峰顶元素- 求取中点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
- 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)
前言 二分法,这一看似简单却又充满哲理的算法,犹如一道精巧的数学之门,带领我们在问题的迷雾中找到清晰的道路。它的名字虽简单,却深藏着智慧的光辉。在科学的浩瀚星空中,二分法如一颗璀璨的星辰,指引着我们…...

# 01_Python基础到实战一飞冲天(三)--python面向对象(一)--简单类
01_Python基础到实战一飞冲天(三)–python面向对象(一)–简单类 一、面向对象-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 。该矩阵具有以下特性: 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 代码思路: 用暴力算法: class Solution {public boolean searchMatrix(…...

Python语法基础(四)
🌈个人主页:羽晨同学 💫个人格言:“成为自己未来的主人~” 高阶函数之map 高阶函数就是说,A函数作为B函数的参数,B函数就是高阶函数 map:映射 map(func,iterable) 这个是map的基本语法,…...
03_Django视图
三、Django模板 模板Templates 在Django框架中,模板是可以帮助开发者快速生成呈现给用户页面的工具 模板的设计方式实现了我们MVT中VT的解耦(M:Model,V:View,T:Template),VT有着N:M的关系,一个V可以调用任意T…...

如何从 Hugging Face 数据集中随机采样数据并保存为新的 Arrow 文件
如何从 Hugging Face 数据集中随机采样数据并保存为新的 Arrow 文件 在使用 Hugging Face 的数据集进行模型训练时,有时我们并不需要整个数据集,尤其是当数据集非常大时。为了节省存储空间和提高训练效率,我们可以从数据集中随机采样一部分数…...
11 设计模式之代理模式(送资料案例)
一、什么是代理模式? 在现实生活中,我们常常遇到这样的场景:由于某些原因,我们可能无法亲自完成某个任务,便会委托他人代为执行。在设计模式中,代理模式 就是用来解决这种“委托”问题的࿰…...

MongoDB聚合操作
1.聚合操作 聚合操作处理数据记录并返回计算结果。聚合操作组值来自多个文档,可以对分组数据执行各种操作以返回单个结果。聚合操作包含三类:单一作用聚合、聚合管道、MapReduce。 单一作用聚合:提供了对常见聚合过程的简单访问,…...
第二十三周周报:High-fidelity Person-centric Subject-to-Image Synthesis
目录 摘要 Abstract TDM SDM SNF 测试时的人物细节捕捉 主要贡献 总结 摘要 本周阅读了一篇2024年CVPR的关于高保真度、以人物为中心的图像合成方法的论文:High-fidelity Person-centric Subject-to-Image Synthesis。该论文提出了一种名为Face-diffuser的…...
Cesium 与 Leaflet:地理信息可视化技术比较
在现代地理信息系统(GIS)和空间数据可视化领域,Cesium 和 Leaflet 是两种非常常见的地理可视化库,它们各自适用于不同的应用场景。Cesium 专注于三维地球视图和复杂空间分析,而 Leaflet 则注重轻量级的二维地图展示。本文将对这两种技术进行详细的对比,帮助开发者根据具体…...

Linux 服务器使用指南:诞生与演进以及版本(一)
一、引言 在当今信息技术的浪潮中,Linux 操作系统无疑是一个关键的支柱😎。无论是在服务器管理、软件开发还是大数据处理领域,Linux 都以其卓越的适应性和优势脱颖而出👍。然而,对于许多新手而言,Linux 系统…...
龙蜥 Linux 安装 JDK
龙蜥 Linux 安装 JDK 下载安装解压到目标路径设置环境变量直接在启动脚本中临时设置 参考资料 下载 这个就不赘述了,参考资料中的另外两篇安装帖,都有。 如果不能上网,也可以去内网其他之前装过JDK的服务器,直接复制过来。 tar …...
Python小白语法基础20(模块与包)
0) 参考文章 python的模块(module)、包(package)及pip_python package-CSDN博客Python之函数、模块、包库_python函数、模块和包-CSDN博客Python函数模块自定义封装及模块嵌套导入(手把手教程)_python如何封装一个模块-CSDN博客 1) 模块与包说明 软件…...
详解 Qt QtPDF之QPdfPageNavigator 页面跳转
文章目录 前言头文件: 自 Qt 6.4 起继承自: 属性backAvailable : const boolcurrentLocation : const QPointFcurrentPage : const intcurrentZoom : const qrealforwardAvailable : const bool 公共函数QPdfPageNavigator(QObject *parent)virtual ~QPd…...

通俗易懂:序列标注与命名实体识别(NER)概述及标注方法解析
目录 一、序列标注(Sequence Tagging)二、命名实体识别(Named Entity Recognition,NER)**命名实体识别的作用****命名实体识别的常见实体类别** : 三、标签类型四、序列标注的三种常见方法1. **BIO…...

【C语言】二叉树(BinaryTree)的创建、3种递归遍历、3种非递归遍历、结点度的实现
代码主要实现了以下功能: 二叉树相关数据结构定义 定义了二叉树节点结构体 BiTNode,包含节点数据值(字符类型)以及指向左右子树的指针。 定义了顺序栈结构体 SqStack,用于存储二叉树节点指针,实现非递归遍历…...

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

重生之我在异世界学编程之C语言:二维数组篇
大家好,这里是小编的博客频道 小编的博客:就爱学编程 很高兴在CSDN这个大家庭与大家相识,希望能在这里与大家共同进步,共同收获更好的自己!!! 本文目录 引言正文一 二维数组的创建1. 二维数组的…...

和鲸科技创始人CEO范向伟出席首届工业智算产业发展研讨会,共话 AI 创新与产业化落地
11 月 22 日,首届工业智算产业发展研讨会在中国工业互联网研究院召开。工业和信息化部党组成员、副部长单忠德,国家信息中心大数据发展部副主任魏颖出席会议并致辞。中国工程院院士、北京化工大学教授高金吉,工业和信息化部信息通信发展司二级…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...