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

二分查找模板--从题目中讲解三大二分模板

news 来源：原创 2025/7/19 19:10:33

二分查找的特点：最恶心、细节最多、最容易写出死循环的算法

1.朴素的二分模板

1.1题目链接：704.二分查找

1.2题目描述：

1.3算法流程：

1.4算法代码：

1.5朴素二分模板：

2.查找左,右边界的二分模板

2.1题目链接：34.在排序数组中查找元素的第一个和最后一个位置

2.2题目描述：

2.3算法思路：

2.4算法代码

2.5左右边界的二分模板：

2.6左右边界模板的记忆方法：

1.朴素的二分模板

1.1题目链接：704.二分查找

1.2题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

1.3算法流程：

a.定义left，right指针分别指向数组的左右区间。

b.找到待查找区间的中间点mid，找到之后分三种情况讨论：

arr[mid] == target说明正好找到，返回mid的值；
arr[mid] > target 说明[mid，right]这段区间都大于target的，因此舍去右边区间，在左边[left, mid-1]的区间继续查找，即让right = mid - 1，然后重复2过程
arr[mid] < target 说明[left，mid]这段区间的值都是小于target的，因此舍去左边区间，在右边[mid+1,right]区间继续查找，即让left = mid+1，然后重复2过程；

c.当left和right错开时，说明整个区间都没有这个数，返回-1

1.4算法代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0,right = nums.size()-1;while(left<=right){int mid = left + (right-left)/2;//防止溢出if(target>nums[mid]){left = mid+1;}else if(target < nums[mid]){right = mid-1;}elsereturn mid;}return -1;}
};

1.5朴素二分模板：

while(left <= right)
{int mid = left + (right - left) / 2;if(....)left = mid + 1;else if(...)right = mid - 1;elsereturn.....;
}

2.查找左,右边界的二分模板

2.1题目链接：34.在排序数组中查找元素的第一个和最后一个位置

2.2题目描述：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

2.3算法思路：

用的还是二分思想，就是根据数据的性质，在某种判断条件下将区间一分为二，然后舍去其中一个区间，然后再另一个区间内查找；

方便描述，用x表示该元素，resLeft表示左边界，resRight表示右边界。

寻找左边界思路：
我们注意到左边界划分的两个区间的特点：

左边区间[left,resLeft - 1]都是小于x的；
右边区间(包括左边界)[resLeft，right]都是大于等于x的；

因此，关于mid的落点，我们可以分为下面两种情况：

当我们mid落在[left,resLeft - 1]区间的时候，也就是arr[mid] < target。说明[left,mid]都是可以舍去的，此时更新left到mid+1的位置，继续再[mid+1，right]上寻找左边界；
当mid落在[resLeft, right]的区间的时候，也就是arr[mid] >= target。说明[mid+1，right]（因为mid可能是最终结果，不能舍去）是可以舍去的，此时更新right到mid的位置，继续在[left, mid]上寻找左边界；
由此，就可以通过二分，来快速寻找左边界；

注意：这里找中间元素需要向下取整

因为后续移动左右指针的时候：

左指针：left = mid+1，是会向后移动的，因此区间是会缩小的；
右指针：right = mid，可能会原地踏步(比如：如果向上取整的话，如果剩下1，2两个元素，left == 1，right == 2，mid == 2.更新区间之后，left，right，mid的值没有改变，就会陷入死循环)

因此一定要注意，当right = mid的时候，要向下取整。

寻找右边界思路：

寻右边界：

用resRight表示右边界；

我们注意到右边界的特点：

左边区间(包括有边界)[left,resRight]都是小于等于x的；
右边区间[resRight+1,right]都是大于x的；

因此，关于mid的落点，我们可以分为下面两种情况：

当我们的mid落在[left,resRight]区间的时候，说明[left，mid-1](mid不可以舍去，因为有可能是最终结果)都是可以舍去的，此时更新left到mid的位置。
当mid落在[resRight+1，right]的区间的时候，说明[mid，right]内的元素是可以舍去的，此时更新right到mid-1的位置；

由此，就可以通过二分，来快速寻找右边界；

注意：这里找中间元素需要向上取整。

左值真：left = mid，可能会原地踏步(比如：如果向下取整的话，如果剩下1，2两个元素，left == 1，right == 2，mid == 1。更新区间之后，left，right，mid的值没有改变，就会陷入死循环)。
右指针：right = mid-1，是会向前移动的，因此区间是会缩小的；

因此一定要注意，当right = mid的时候，要向下取整。

2.4算法代码

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0){return {-1,-1};}int begin = 0;//1.二分左端点int left = 0,right = nums.size()-1;while(left < right){int mid = left + (right - left)/2;if(nums[mid]>=target)right = mid;elseleft = mid+1;       }//判断是否有结果if(nums[left] != target) return {-1,-1};else begin = left;left = 0,right = nums.size()-1;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid]>target)right = mid-1;elseleft = mid;}return {begin,right};}
};

2.5左右边界的二分模板：

//寻找左边界
while (left < right)
{int mid = left + (right - left) / 2;if (......)left = mid + 1;else right = mid;
}
//寻炸右边界
while (left < right)
{int mid = left + (right - left +1) / 2;if (......)left = mid;else right = mid - 1;
}

2.6左右边界模板的记忆方法：

当只有两个元素，left指向左边的元素，right指向右边的元素。因为只有当left = right的时候才是找到边界。所以

当mid指向左边的元素时，想要left = right，就必须right = mid，且right向左，所以是寻找左边界且right = mid,left = mid+1。

当mid指向右边的元素时，想要left = right，就必须left = mid，且left向左，所以是寻找右边界且left = mid，right = mid-1。

mid指向右边的是，mid = left +（right-left+1)/2

mid指向左边的是，mid = left + (right - left)/2

二分查找模板--从题目中讲解三大二分模板

二分查找的特点：最恶心、细节最多、最容易写出死循环的算法目录 1.朴素的二分模板 1.1题目链接：704.二分查找 1.2题目描述： 1.3算法流程： 1.4算法代码： 1.5朴素二分模板： 2.查找左,右边界的二分模板…...

编程日记 2025/7/19 19:10:33

EF Core 执行原生SQL语句

文章目录前言一、执行查询（返回数据）1） 使用 FromSqlRaw或 FromSqlInterpolated 方法，适用于 DbSet<T>，返回实体集合。2）结合 LINQ 查询3）执行任意原生SQL查询语句（使用ADO.N…...

编程日记 2025/7/19 19:00:03

HiveChat：提升团队协作效率的AI聊天应用

什么是 HiveChat ？ HiveChat 作为一款专为中小团队设计的 AI 聊天应用，支持 Deepseek、Open AI、Claude、Gemini 等模型。管理员一人配置，全团队轻松使用各种 AI 模型。凭借其强大的功能和便捷的操作，有望成为团队沟通协作的得力助…...

编程日记 2025/7/19 18:43:12

python中的继承

目录一、继承单继承多继承方法的重写一、继承在Python中，继承是面向对象编程中的重要概念，它允许一个类（子类）继承另一个类（父类）的属性和方法。子类可以继承父类的属性和方法，并且可…...

编程日记 2025/7/19 13:09:40

Vulnhub靶场FALL靶机通关攻略

1.打开靶机和kali 2.扫描靶机ip 靶机ip为192.168159.158 3.访问下网站翻阅一下可能存在后门网站根目录下可能有线索 4.爆破目录 ir -u http://192.168.159.158 -w /usr/share/wordlists/dirbuster/directory-list-2.3-medium.txt -x .php,.bak,.txt,.sh,.ht…...

编程日记 2025/7/17 1:17:47

Java基础概念汇总

JavaEE Java基础概念面试题详解1. Java的特点是什么？2. Java和C的区别有哪些？3. 什么是JDK、JRE和JVM？它们之间有什么关系？4. Java是编译型语言还是解释型语言？5. Java如何实现跨平台？ 数据类型与变量面试题…...

编程日记 2025/7/19 19:04:42

【服务端】使用conda虚拟环境部署Django项目

写在开头为了与客户端的Deep search配合，需要整一个后台管理来保存和管理deep search的数据资料。选择前端框架Vue-Vben-Admin Django后台服务来实现这个项目。废话结束，从零开始。。。。一、环境搭建 1. 安装 Anaconda 下载 Anaconda&#xff1…...

编程日记 2025/7/19 18:36:05

基于Pycatia的智能孔特征识别技术：无参模型圆心自动化提取方案

引言本文介绍了一种基于Pycatia二次开发的无参数模型孔特征识别技术，通过拓扑分析与几何特征检测双验证机制，实现圆形孔边线的精准识别及圆心坐标自动化生成。该方案可有效解决逆向工程、质量检测等场景下非参数化模型的孔位分析难题，提升三…...

编程日记 2025/7/19 19:03:34

cpu 比较低，load 比较高怎么解决

当系统出现 CPU 使用率低但 Load Average（系统负载）高的情况时，通常意味着系统资源瓶颈不在 CPU，而可能出现在其他环节（如 I/O 等待、锁竞争、大量进程排队等）。以下是排查和解决问题的详细步骤：一、理解 Load Average 的含义 Linux 系统的 Load Average 表示单位时…...

编程日记 2025/7/15 18:21:53

qt QQuaternion详解

1. 概述 QQuaternion 是 Qt 中用于表示三维空间中旋转的四元数类。它包含一个标量部分和一个三维向量部分，可以用来表示旋转操作。四元数在计算机图形学中广泛用于平滑的旋转和插值。 2. 重要方法默认构造函数 QQuaternion::QQuaternion(); // 构造单位四元数 (1…...

编程日记 2025/7/14 11:34:06

伊利工业旅游4.0，近距离感受高品质的魅力

3月24日，在2025年第112届全国糖酒会（简称春糖）前夕，伊利集团“可感知高品质探寻荟”活动在成都召开，记者走进伊利在西南地区最大的乳制品生产基地—邛崃工厂，零距离见证液态奶、酸奶、冷饮等乳制品的诞生&a…...

编程日记 2025/7/16 1:48:58

前端面经分享（25/03/26）

北京一家做AI解决方案的公司，技术一面，15k-20k，要求3-5年你们React项目里路由模式用的什么React里class组件和function组件都用过吗常用Hook，解释一下他们的作用useEffect第二个参数填空数组和不填有什么区别React组件通信的常用…...

编程日记 2025/7/19 19:08:10

unity实现图片查看器有限制的移动缩放功能

需求 unity实现键盘wasd键控制图片的移动，图片长度未超出屏幕不能移动，宽度未超出屏幕不能移动。jk键控制图片的缩放，缩放有限制 using UnityEngine;public class ImageController : MonoBehaviour {[Header("移动设置")]public f…...

编程日记 2025/7/19 18:48:03

STM32基础教程——输入捕获模式测量PWM频率

目录前言技术实现原理图连线图代码实现内容要点 PWM基本结构开启外设时钟配置GPIO端口配置时基单元初始化输出比较单元输出比较通道重映射输入捕获功能初始化计算捕获PWM的频率实验结果问题记录前言 IC（Input Capture）输…...

编程日记 2025/7/19 18:55:21

【redis】集群如何搭建集群详解

文章目录集群搭建1. 创建目录和配置2. 编写 docker-compose.yml完整配置文件 3. 启动容器4. 构建集群超时集群搭建基于 docker 在我们云服务器上搭建出一个 redis 集群出来当前节点，主要是因为我们只有一个云服务器，搞分布式系统，就比较…...

编程日记 2025/7/19 19:09:19

Linux应用：线程基础

线程介绍进程是程序在操作系统里的一次执行过程，是系统进行资源分配和调度的基本单位；而线程是进程中的一个执行单元，是 CPU 调度和分派的基本单位。一个进程可以包含多个线程，这些线程共享进程的资源，如内存空间、文…...

编程日记 2025/7/19 18:55:19

力扣HOT100之普通数组：238. 除自身以外数组的乘积

这道题不能使用除法，我第一时间想到用前缀表和后缀表来解决，假设数组nums的长度为n，我们直接定义前缀表pre和后缀表suf，其中pre[i] pre[i - 1] * nums[i - 1] nums[0] * nums[1] * ... * nums[i - 1] ，而suf[j] suf…...

编程日记 2025/7/19 19:01:15

PHP回调后门小总结

目录 1.call_user_func 函数说明蚁剑连接 2.数组操作造成的单参数回调后门 array_filter 函数说明蚁剑连接 array_map 函数说明蚁剑连接 3.二参数回调函数 uasort 函数说明 uksort array_reduce array_udiff 蚁剑连接 4.三参数的回调后门 array_walk 函数说…...

编程日记 2025/7/19 19:09:20

《深度剖析SQL数据类型转换：隐式与显式的奥秘》

在SQL的世界里，数据类型转换是一个基础且关键的操作，它贯穿于数据库开发、管理与数据分析的各个环节。数据类型转换分为隐式转换和显式转换，二者各有特点与应用场景，深刻理解它们对于编写高效、稳定的SQL代码至关重要。一、数据…...

编程日记 2025/7/19 1:18:26

通过TIM+DMA Burst 实现STM32输出变频且不同脉冲数量的PWM波形

Burst介绍： DMA控制器可以生成单次传输或增量突发传输，传输的节拍数为4、8或16。为了确保数据一致性，构成突发传输的每组传输都是不可分割的：AHB传输被锁定，AHB总线矩阵的仲裁器在突发传输序列期间不会撤销DMA主设备…...

编程日记 2025/7/16 17:12:05

多线程 --- 多线程编程

在写代码的时候，可以使用多进程进行并发编程（在Java中，不太推荐，很多很多关于进程相关的API，在Java标准库中，都没有提供），也可以使用多线程进行并发编程（系统提供了多线程…...

编程日记 2025/7/19 18:51:34

利用新一代雷达传感器增强ADAS系统的检测和计算（TI文档）

摘要德州仪器 (TI) 的新一代雷达传感器AWR2E44P和AWR2944P推动了TI的ADAS雷达产品系列发展，专注于提高性能以满足严格的 NCAP（新车评估计划）和 FMVSS（联邦机动车辆安全标准）自动驾驶和安全法规。这些雷达器件为 AWR…...

编程日记 2025/7/15 22:35:54

前端工程化开篇

前端发展史梳理： 最早的html，css，js是前端三剑客，足以实现所有的前端开发任务，但是呢，一个简单的前端交互效果可能就需要一大堆的代码去实现。后来呢，有了前端库jQuery，他可以使前…...

编程日记 2025/7/19 19:08:09

Android 问真八字-v2.1.7[看八字APP]

Android 问真八字链接：https://pan.xunlei.com/s/VOMMuCVQRQrM2vRsHj14SsO0A1?pwdavzw# Android 问真八字-v2.1.7[看八字APP]...

编程日记 2025/7/19 19:02:21

go - grpc入门

前期准备工具安装及使用 grpc开发编写proto文件 proto文件是符合Protocol Buffers语言规范的数据交换协议文件，就像以前WebService定义服务时使用的XML文件。现在一般都是用proto3了，这里创建一个名为 hello.proto 的文件，放到项目的pr…...

编程日记 2025/7/19 19:05:53

操作系统环境：CentOS 7.2 本地yum源配置 1.挂载镜像 mount /dev/cdrom /mnt/cdrom 2.备份原yum配置 mv /etc/yum.repos.d /etc/yum.repos.d.bak 3.创建本地yum源配置文件 mkdir /etc/yum.repos.d vi /etc/yum.repos.d/CentOS-local.repo 添加内容： #本…...

编程日记 2025/7/17 16:50:39

【活动回顾】StarRocks Singapore Meetup #2 @Shopee

3 月 13 日，StarRocks 社区在新加坡成功举办了第二场 Meetup 活动，主题为“Empowering Customer-Facing Analytics”。本次活动在 Shopee 新加坡办公室举行，吸引了来自 Shopee、Grab 和 Pinterest 的专家讲师以及 50 多位参会者。大家围绕电商…...

编程日记 2025/7/19 18:46:51

优选算法——双指针专题

本章先分享关于优选算法的双指针的思路： 主要是以题目来展示常见使用双指针的思路。 ps: 双指针做法：不要被表面所迷惑，它其实是通过用一个数组的下标来充当指针数组分两块：是⾮常常⻅的⼀种题型，主要就是根据⼀种…...

编程日记 2025/7/19 19:05:55

深度解析：TOML、XML、YAML及其他配置/数据格式对比

深度解析：TOML、XML、YAML及其他配置/数据格式对比在软件开发和系统配置中，选择合适的配置或数据格式至关重要。本文将对比 TOML、XML、YAML 等常见格式，梳理它们的核心特性、适用场景及区别，并扩展介绍其他类似格式&#xff0c…...

编程日记 2025/7/19 18:35:22

冗余技术：堆叠技术+链路聚合

目录前言一.堆叠技术概述二.堆叠技术原理三.堆叠系统登录四.堆叠合并/分裂 4.1 堆叠双主检测机制（MAD） 五.链路聚合技术概述六.链路聚合模式前言在硬件加速与数据爆炸时代，堆叠技术通过模块化分层设计，实现资源动…...

编程日记 2025/7/15 20:21:30

存储服务器是指什么

今天小编主要来为大家介绍存储服务器主要是指什么，存储服务器与传统的物理服务器和云服务器是不同的，其是为了特定的目标所设计的，在硬件配置方式上也有着一定的区别，存储空间会根据需求的不同而改变。存储服务器中一般会配备大容…...

编程日记 2025/7/19 18:51:34

文件上传绕过的小点总结(8)

16.apache解析漏洞条件竞争 class MyUpload{.................. var $cls_arr_ext_accepted array(".doc", ".xls", ".txt", ".pdf", ".gif", ".jpg", ".zip", ".rar", ".7z",&q…...

编程日记 2025/7/19 19:09:21

设计模式-结构型模式-外观模式

概述外观模式 : Facade Pattern : 是一种结构型设计模式. 它为复杂子系统提供一个简化的统一接口，使得客户端无需直接与子系统的各个组件交互，从而降低系统的耦合性。核心思想统一接口：将多个子系统的复杂操作封装到一个“外观类”中&…...

编程日记 2025/7/19 19:05:52

DeepSeek 本地部署指南

文章目录 DeepSeek 本地部署指南一、前言二、部署前的准备工作2.1 硬件要求2.2 软件环境三、模型下载四、本地部署步骤4.1 检查硬件加速支持4.2 部署模型4.3 优化部署五、常见问题及解决方法5.1 内存不足5.2 模型下载失败5.3 GPU 无法使用六、总结 DeepSeek 本地部署指南一…...

编程日记 2025/7/19 19:02:22

Windows Server 2025 使用 IIS 搭建 ASP.NET 3.5 网站

开启远程桌面参考文章Windows server开启远程桌面教程打开服务管理器。ECS 配置安全组，开启 3389Telnet 验证网络联通性 telnet x.x.x.x 338安装 Windows App，登录验证安装 ASP.NET 3.5 1.参考文章Windows Server 2012安装 .NET Framework 3.5和 Wi…...

编程日记 2025/7/17 7:13:06

python每日十题(12)

根据字典的索引方式可知，d.get( egg ,no this food)索引的是字典第一层，但是第一层只有键food，没有键egg，故索引不出值，输出的是“no this food ”。外层for循环是将a[0][1,2,3],a[1][4,5,6],a[2][7,8,9]依次赋给变量…...

编程日记 2025/7/19 19:10:32

Podman 学习总结

Podman 概述什么是 Podman？ Podman（Pod Manager）是一个开源的容器管理工具，类似于 Docker，可以用于拉取、运行、管理容器镜像。Podman 采用无守护进程****（Daemonless） 的架构，使…...

编程日记 2025/7/19 18:58:56

作业14 （2023-05-22_const修饰指针）

第1题/共5题【单选题】 C程序常见的错误分类不包含：（） A.编译错误 B.链接错误 C.栈溢出 D.运行时错误回答正确答案解析：栈溢出是运行时错误的一种，因此C程序不会将栈溢出错误单独列出来，栈溢出包含在运行时错误中。因此：选择C 第2题/共5题【单选题】以下关于…...

编程日记 2025/7/19 19:10:32

Qt 线程和 QObjects

线程和 QObjects QThread 继承于 QObject。它发出信号来指示线程开始或结束执行，并提供一些插槽。更有趣的是，QObjects 可以在多个线程中使用，发出信号以调用其他线程中的插槽，并向 "生活 "在其他线程中的对象发布事件…...

编程日记 2025/7/16 5:20:12

cocos creator 笔记-路边花草

版本：3.8.5 实现目标：给3d道路生成路边景观花草在场景下创建一个节点，我这里种植两种花草模型，兰花和菊花，所以分别在节点下另创建两个节点，为了静态合批。 1.将花草模型分别拖入场景中，制作…...

编程日记 2025/7/17 14:51:07

基于SpringBoot+Vue3实现的宠物领养管理平台功能十六

一、前言介绍： 1.1 项目摘要随着社会经济的发展和人们生活水平的提高，越来越多的人开始关注并参与到宠物领养中。宠物已经成为许多家庭的重要成员，人们对于宠物的关爱和照顾也日益增加。然而，传统的宠物领养流程存在诸多不便&a…...

编程日记 2025/7/17 11:22:57

MOSN（Modular Open Smart Network）-05-MOSN 平滑升级原理解析

前言大家好，我是老马。 sofastack 其实出来很久了，第一次应该是在 2022 年左右开始关注，但是一直没有深入研究。最近想学习一下 SOFA 对于生态的设计和思考。 sofaboot 系列 SOFAStack-00-sofa 技术栈概览 MOSN（Modular O…...

编程日记 2025/7/15 5:58:41

数据仓库pinia中，getter和actions有什么区别

将计算逻辑放在 getters 还是 actions 里，取决于具体的使用场景和需求，下面详细分析放在 getters 中的优势以及和 actions 的区别，以说明是否有必要放在 getters 里： 1. getters 的优势缓存特性 getters 具有类似 Vue 计算属性…...

编程日记 2025/7/15 5:47:23

RoMA: 基于Mamba的遥感基础模型, 已开源, 首次验证mamba的scaling能力

Time: 2025-03-27T15:27:00 github: 链接 HuggingFace: 链接摘要近年来，自监督学习在视觉 Transformer（ViT）方面的进展推动了遥感（RS）基础模型的突破。然而，自注意力机制的二次复杂度给可扩展性带来了…...

编程日记 2025/7/14 1:32:04

蓝桥杯(电子类)嵌入式第十一届设计与开发科目模拟试题

一、功能概览二、分模块实现 1、按键新建interrupt.h和interrupt.c写中断的代码（写法学习来自定时器-按键单击_哔哩哔哩_bilibili） #ifndef __INTERRUPT_H #define __INTERRUPT_H#include "main.h" #include "stdbool.h"struct…...

编程日记 2025/7/17 7:46:33