二分查找的边界问题
前言
二分查找(Binary Search)是一种高效的查找算法,时间复杂度为O(log n)。它适用于已排序的数组或列表。本文将详细介绍二分查找的两种常见写法:闭区间写法和左闭右开区间写法。
一、二分查找基本思想
二分查找的核心思想是"分而治之":
- 将查找区间分成两部分
- 比较中间元素与目标值
- 根据比较结果决定继续在左半部分或右半部分查找
- 重复上述过程直到找到目标值或确定目标值不存在
二、闭区间写法 [left, right]
闭区间写法中,查找区间包含左右边界,即[left, right]
。
代码实现
#include <vector>
using namespace std;int binarySearchClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 闭区间包含右边界while (left <= right) { // 1.注意是<=int mid = left + (right - left) / 2; // 2.防止溢出if (nums[mid] == target) {return mid; // 找到目标} else if (nums[mid] < target) {left = mid + 1; // 3.搜索右半部分} else {right = mid - 1; // 4.搜索左半部分}}return -1; // 未找到
}
关键点说明
-
初始化:
right = len(nums) - 1
,因为要包含最后一个元素 -
循环条件:
left <= right
,因为当left == right
时区间[left, right]
仍然有效 -
边界更新:
left = mid + 1
:因为nums[mid]
已经检查过,可以排除right = mid - 1
:同理
三、左闭右开区间写法 [left, right)
左闭右开区间写法中,查找区间包含左边界但不包含右边界,即[left, right)
。
代码实现
int binarySearchLeftClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 右边界不包含while (left < right) { // 注意是<int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid; // 注意不是mid-1}}return -1;
}
关键点说明
-
初始化:
right = len(nums)
,因为右边界不包含 -
循环条件:
left < right
,因为当left == right
时区间[left, right)
无效 -
边界更新:
left = mid + 1
:与闭区间相同right = mid
:因为右边界不包含,所以不需要mid - 1
四、两种写法的比较
特性 | 闭区间写法 | 左闭右开区间写法 |
---|---|---|
初始化右边界 | len(nums)-1 | len(nums) |
循环条件 | left <= right | left < right |
右边界更新 | right = mid - 1 | right = mid |
区间含义 | [left, right] | [left, right) |
终止条件 | left > right | left == right |
五、实际应用中的选择
两种写法都是正确的,选择哪一种主要取决于个人习惯和具体场景:
-
闭区间写法:
- 更直观,区间定义明确
- 边界更新对称(left=mid+1, right=mid-1)
-
左闭右开区间写法:
- 右边界初始化更简单(直接使用nums.size)
- 在某些变种问题中可能更方便
六、例题展示
例题链接:704. 二分查找 - 力扣(LeetCode)
解答:
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = (right - left) / 2 + left;int num = nums[mid];if (num == target) {return mid;} else if (num > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
};
七、常见错误与注意事项
- 溢出问题:计算mid时使用
left + (right - left) // 2
而不是(left + right) // 2
,防止left和right很大时相加溢出 - 边界更新错误:确保在左闭右开写法中不要错误地使用
right = mid - 1
- 循环条件混淆:注意两种写法的循环条件不同
- 未排序数组:二分查找要求输入数组必须是有序的
八、总结
二分查找是一种高效且常用的算法,掌握其两种区间写法对于解决各种变种问题非常有帮助。理解区间定义和边界更新规则是关键,建议通过大量练习来熟练掌握这两种写法。
希望这篇博客能帮助你更好地理解二分查找算法!在实际编程中,可以根据具体情况和个人偏好选择适合的写法。
相关文章:
二分查找的边界问题
前言 二分查找(Binary Search)是一种高效的查找算法,时间复杂度为O(log n)。它适用于已排序的数组或列表。本文将详细介绍二分查找的两种常见写法:闭区间写法和左闭右开区间写法。 一、二分查找基本思想 二分查找的核心思想是"分而治之"&am…...
应用示例1:交通灯
基于FPGA的交通灯控制系统实现原理详解 目录 基于FPGA的交通灯控制系统实现原理详解一、项目简介二、数字电路与基础知识1. 交通灯系统的有限状态机(FSM)2. 数码管显示原理3. 二进制转BCD显示4. 时钟与分频三、功能需求与系统结构功能需求系统结构四、各模块设计原理说明1. 时…...
Docker 介绍与使用
Docker 文章目录 Docker介绍与虚拟机的比较启动速度占用资源 优势更容易迁移更容易维护更容易扩展 使用场景持续集成提供可伸缩的云服务搭建微服务架构 镜像与容器镜像构成(分层结构)镜像与容器的区别 安装 Docker常用命令介绍镜像相关容器相关 实战&…...
[数据结构]6. 队列-Queue
队列-Queue 1. 介绍2. 队列实现2.1 基于链表的实现2.2 基于数组的实现 3. 队列操作CreateInitializeDestoryPushPopFrontBackSizeEmpty 1. 介绍 队列(queue) 是一种遵循先入先出规则的线性数据结构。将队列头部称为“队首”,尾部称为“队尾”…...
mybatis plus (sqlserver) 根据条件来获取id最大的,或者是新增的最新的一条记录(同条件可能会有多条出现)
1、mysql的版本 limit 1 QueryWrapper<Userinfo> queryWrapper new QueryWrapper<>();queryWrapper.eq("fid", payment.getFid());return userinfoMapper.selectOne(queryWrapper.orderByDesc("id").last("limit 1")); 只要类似以…...
打卡DAY25
DAY 25 异常处理 知识点回顾: 1. 异常处理机制 2. debug过程中的各类报错 3. try-except机制 4. try-except-else-finally机制 在即将进入深度学习专题学习前,我们最后差缺补漏,把一些常见且重要的知识点给他们补上,加深…...
【C语言指针超详解(六)】--sizeof和strlen的对比,数组和指针笔试题解析,指针运算笔试题解析
目录 一.sizeof和strlen 1.1--sizeof 1.2--strlen 1.3--sizeof和strlen的对比 二.数组和指针笔试题解析 2.1--一维数组 2.2--字符数组 2.2.1--代码1: 2.2.2--代码2: 2.2.3--代码3: 2.2.4--代码4 : 2.2.5--代码5&#…...
Java 异常处理之 BufferUnderflowException(BufferUnderflowException 概述、常见发生场景、避免策略)
一、BufferUnderflowException 概述 BufferUnderflowException 是 Java NIO 包中的一个运行时异常,是 RuntimeException 的子类 public class BufferUnderflowException extends RuntimeException {... }# 继承关系java.lang.Object-> java.lang.Throwable->…...
OpenCV人脸识别LBPH算法原理、案例解析
文章目录 前言一、LBPH 算法原理概述1、LBP 特征计算2、均匀模式与旋转不变性3、直方图统计与识别 二、环境准备1、安装依赖2、数据集结构 三、代码实现(完整代码约 150 行)1、导入库与配置2、加载数据与标签生成3、 模型训练与保存4、 实时人脸识别5、主…...
Lightpanda开源浏览器:专为 AI 和自动化而设计的无界面浏览器
一、软件介绍 文末提供程序和源码下载 Lightpanda开源浏览器:专为 AI 和自动化而设计的无界面浏览器; Javascript execution Javascript 执行Support of Web APIs (partial, WIP)支持 Web API(部分、WIP)Compatible with Pla…...
Docker 疑难杂症解决指南:从入门到进阶的全面剖析
Docker 作为容器化技术的代表,凭借其轻量级、可移植性和高效资源利用率,已成为开发、测试和部署应用的标准工具。然而,在实际使用中,用户常常会遇到镜像构建失败、容器启动异常、网络配置问题等疑难杂症。本文将从镜像构建、容器生…...
CodeBuddy Craft,我的编程搭子
我正在参加CodeBuddy「首席试玩官」内容创作大赛,本文所使用的 CodeBuddy 免费下载链接:腾讯云代码助手 CodeBuddy - AI 时代的智能编程伙伴 你好,我是悟空。 背景 最近项目组事情挺多,一个人要干多个人的活,而且写…...
如何实现一个运动会计分系统?(C语言版)
一、需求分析 设计一个运动会计分系统,计分信息包括参加学校,参与项目,性别,名次个数,各个学校获得名次信息。该系统具有以下功能 数据录入: 链表或结构体数组组织数据数据报表: 依照规定的报表格式对数据打印报表数据排序: 按照要求对数据进行统计,含简单统计及综合统计…...
linux内核主要由哪五个模块构成?
Linux内核是一个高度模块化的系统,其核心功能通常被划分为以下五大模块,共同协作实现操作系统的基础功能: 1. 进程管理(Process Management) 核心功能:负责进程的创建、调度、终止,以…...
编程日志5.5
树的结构代码 #include<iostream> using namespace std; //由于树的每个结点可能有一些孩子结点,这些孩子结点的数量不确定,所以可以用一个链表来把所有的孩子结点给串起来 //链表结点定义 //这段代码定义了一个结构体ListNode,用于表示链表中的一个结点。这个结构…...
React学习———React.memo、useMemo和useCallback
React.memo React.memo是React提供的一个高阶组件,用于优化函数组件的性能,它通过记忆组件的渲染结果,避免在父组件重新渲染时,子组件不必要的重新渲染 React.memo会对组件的props进行浅比较,如果props没有变化&#…...
OpenCV实现数字水印的相关函数和示例代码
OpenCV计算机视觉开发实践:基于Qt C - 商品搜索 - 京东 实现数字水印的相关函数 用OpenCV来实现数字水印功能,需要使用一些位操作函数,我们需要先了解一下这些函数。 1. bitwise_and函数 bitwise_and函数是OpenCV中的位运算函数之一&…...
【CUDA】Sgemm单精度矩阵乘法(下)
目录 前言1. 优化技巧5:使用register模拟二级缓存(内积转外积)2. 优化技巧6:使用register模拟二级缓存 float43. 优化技巧7:global memory转置再存放shared memory4. 优化技巧8:使用double buffer加速矩阵…...
cursor 学习
参考:AI编程神器!Cursor无限续杯!白嫖白嫖!!!...
学术论文的科研流程概述 视频会议记录
CCF-Talk SPP131期 浙江大学研究员彭思达的报告。 举例视频生成要多快好省。 提升代码能力:先明白基础的函数,可以复现一个网络。最好是实现一个操作系统。...
【Linux笔记】——Linux线程理解与分页存储的奥秘
🔥个人主页🔥:孤寂大仙V 🌈收录专栏🌈:Linux 🌹往期回顾🌹:【Linux笔记】——进程信号的捕捉——从中断聊聊OS是怎么“活起来”的 🔖流水不争,争的…...
ACM算法
在ACM模式下使用JavaScript/TypeScript获取输入值 在ACM编程竞赛或在线判题系统(如LeetCode、牛客网等)中,JavaScript/TypeScript需要特定的方式来获取输入值。以下是几种常见的获取输入的方法: 1. 使用Node.js的readline模块 这是最常见的处理ACM模式…...
家用或办公 Windows 电脑玩人工智能开源项目配备核显的必要性(含 NPU 及显卡类型补充)
一、GPU 与显卡的概念澄清 首先需要明确一个容易误解的概念:GPU 不等同于显卡。 显卡和GPU是两个不同的概念。 【概念区分】 在讨论图形计算领域时,需首先澄清一个常见误区:GPU(图形处理单元)与显卡(视…...
FastByteArrayOutputStream和ByteArrayInputStream有什么区别
FastByteArrayOutputStream 和 ByteArrayInputStream 是两种完全不同的 Java I/O 类,它们的主要区别体现在 设计目的 和 使用场景 上。以下是详细对比: 1. 核心区别总结 特性FastByteArrayOutputStream (Spring框架)ByteArrayInputStream (JDK原生)所属…...
远程连接电脑的方法?异地远程桌面连接和三方软件实现
远程连接电脑,是指通过网络技术,在一台设备上操控另一台设备的电脑桌面,实现跨地域的操作和管理。在日常工作、技术支持、远程办公等场景中,远程连接电脑都发挥着重要作用。实现远程连接电脑主要有系统自带工具和第三方软件两种方…...
编程题 03-树2 List Leaves【PAT】
文章目录 题目输入格式输出格式输入样例输出样例 题解解题思路完整代码 编程练习题目集目录 题目 Given a tree, you are supposed to list all the leaves in the order of top down, and left to right. 输入格式 Each input file contains one test case. For each case, …...
数据预处理之数据平滑处理详解
信号数据收到噪声干扰,影响检测的准确性。数据平滑处理的关键步骤,旨在降低噪声同时保留信号特征。 1.1 移动平均(Moving Average) 原理:通过计算窗口内数据的平均值来平滑噪声,适用于快速去除高频噪声。…...
deepseek梳理java高级开发工程师算法面试题
Java高级工程师算法面试题与答案 一、数据结构与算法基础 1. 红黑树与AVL树比较 题目:详细说明红黑树和AVL树的区别及各自的适用场景,并用Java实现红黑树的插入操作。 答案: 区别对比: ┌─────────────────…...
【SSL证书系列】SSL证书工作原理解读
SSL(Secure Sockets Layer)及其继任者TLS(Transport Layer Security)是用于保护网络通信安全的加密协议。SSL证书是实现HTTPS协议的核心,其工作原理涉及加密技术、身份验证和信任机制。以下是其工作原理的详细分步解析…...
模板源码建站、定制建站和SaaS 建站有什么区别?企业建站应该怎么选?
最近遇到不少客户问,为什么现在做一个网站为什么从几百到几万的都有呀?市面上五花八门有模板源码建站、SaaS建站和定制建站我该怎么选?有什么区别?今天小编就跟大家一起来唠一唠,接下来我们就一起来看看吧!…...
OpenCV进阶操作:人脸检测、微笑检测
文章目录 前言一、OpenCV如何实现人脸检测1、haar特征2、级联分类器3、级联分类器的使用 二、人脸检测、微笑检测 案例实现1、预处理2、加载分类器3、标注人脸4、运行结果:4、微笑检测 总结 前言 要实现人脸识别首先要判断当前图像中是否出现了人脸,这就…...
论文查询的ai工具 —— SCAICH
(1)SCAICH的项目背景 SCAICH是由Scihub Web3 Community孵化的技术产品。SCAICH是一个非盈利性的平台,模式上采用免费邀请码模式,采用捐赠和广告维持成本。产品将会面向世界上所有国家的学者。 (2)SCAICH产品…...
Python+大模型 day01
Python基础 计算机系统组成 基础语法 如:student_num 4.标识符要做到见名知意,增强代码的可读性 关键字 系统或者Python定义的,有特殊功能的字符组合 在学习过程中,文件名没有遵循标识符命名规则,是为了按序号编写文件方便查找复习 但是,在开发中,所有的Python文件名称必须…...
elasticsearch硬件与资源配置优化
以下是Elasticsearch硬件与资源配置优化的综合方案,结合最新实践与核心优化逻辑: 一、硬件选型优化 存储设备 优先选用SSD作为存储介质,其随机读取性能比机械硬盘高5-10倍,尤其适合文档检索类高并发场景。单节点存储控制在2TB以内,避免超过5TB导致查询性能下降和系统…...
C++ 在 Windows 的开发经验与解决方案
一、开发环境搭建 在 Windows 上进行 C 开发,主流的集成开发环境(IDE)有 Visual Studio 和 CLion。Visual Studio 是微软官方推出的强大开发工具,对 Windows 平台有着原生的支持,集成了编译器、调试器、代码编辑器等一…...
1669上什么课
1.题目描述 暑假来了,晶晶报了四门课来充实自己的暑假生活;周一上游泳,周三上编程,周五上阅读,周六上数学;其余时间没课。请从键盘读入今天是星期几,输出晶晶今天应该上什么课。 请注意&#…...
通过MCP让LLM调用系统接口
场景 MCP的出现大大丰富了LLM的功能,对于存量系统,我们希望能让模型调用已有的接口,以最小的成本让AI能够获取系统内部数据。因此我们开发了一个名为http-api-call的MCP Server,来支持模型到内部API的调用 实现方案 使用用标准…...
Java NIO 深度解析:突破传统IO的性能瓶颈
一、Java NIO 核心价值与演进历程 1.1 传统IO的局限性 Java传统的BIO(Blocking I/O)模型在应对高并发场景时存在显著缺陷: 线程资源浪费:每个连接需要独立线程处理上下文切换开销:线程数增加导致CPU调度成本指数级增长吞吐量瓶颈:受限于线程池大小和操作系统限制响应延…...
AI-02a5a5.神经网络-与学习相关的技巧-权重初始值
权重的初始值 在神经网络的学习中,权重的初始值特别重要。实际上,设定什么样的权重初始值,经常关系到神经网络的学习能否成功。 不要将权重初始值设为 0 权值衰减(weight decay):抑制过拟合、提高泛化能…...
sqlalchemy库详细使用
SQLAlchemy 是 Python 中最强大、最受欢迎的 ORM(对象关系映射)库,它允许你使用 Python 对象来操作数据库,而不需要直接编写 SQL 语句。同时,它也提供了对底层 SQL 的完全控制能力,适用于从简单脚本到大型企…...
最短路和拓扑排序知识点
1、在一个有权无向图中,如果顶点b到顶点a的最短路径长度是10,顶点c与顶点b之间存在一条长度为3的边。(c与a的最短路径长度不超过13;c与a的最短路径不小于7) 2、我们用一个有向图来表示航空公司所有航班的航线。最适合…...
【Alist+RaiDrive挂载网盘到本地磁盘】
1.安装准备 安装RaiDrive RaiDrive - 像 USB 驱动器一样安装云存储 安装alist 安装方式请查看官网: AList文档 2.启动Alist(docker) docker官网 Install | Docker EngineDocker Desktop | Docker Docs 运行容器 docker run -d --restartalways -v /home/alist:/opt/alist/…...
达梦数据库 【-6111: 字符串转换出错】问题处理
达梦数据库 【-6111: 字符串转换出错】问题处理 问题背景问题分析问题总结 问题背景 今天在更新数据库某一个值属性的时候,执行更新语句报错提示 -6111: 字符串转换出错,但是自己检查了sql语句,只是一个简单的sql,并没有需要字符…...
Java的多线程笔记
创建一个线程的方法有多种,比如可以继承Thread类或者实现Runnable接口,结论是实现Runnable接口比前者更加优越。 二者代码对比 Java 不支持多继承,如果你继承了 Thread 类,就不能再继承其他类,实现 Runnable 接口后&am…...
学习51单片机01(安装开发环境)
新学期新相貌.......哈哈哈,我终于把贪吃蛇结束了,现在我们来学stc51单片机! 要求:c语言的程度至少要到函数,指针尽量!如果c语言不好的,可以回去看看我的c语言笔记。 1.开发环境的安装&#x…...
互联网协议的多路复用、Linux系统的I/O模式
目录 1. 互联网协议栈-多路复用 1.1. 应用层的多路复用 2.2. 传输层的多路复用 3.3. 网络层的多路复用 2. Linux系统的I/O模式 2.1. I/O 2.2. Socket 2.3. 从网卡到操作系统 2.4. Socket 编程模型 2.5. I/O多路复用 2.6. 阻塞/非阻塞、同步/异步 2.7. Question 1. …...
vue中,created和mounted两个钩子之间调用时差值受什么影响
在 Vue 中,created 和 mounted 是两个生命周期钩子,它们之间的调用时差主要受以下几个因素影响: 🟢 1. 模板复杂度与渲染耗时(最主要因素) mounted 的触发时间是在组件的 DOM 被挂载之后(也就是…...
软件设计师考试《综合知识》计算机编码考点分析——会更新软设所有知识点的考情分析,求个三连
2019-2023年真题深度解析与备考策略 分值占比分析 75分中编码相关分值分布与核心考点 年份编码相关题量分值占总分比例核心考点20232题2分2.67%补码表示范围、IEEE 754偏移量20223题3分4.00%原码/反码比较、浮点数规格化20211题1分1.33%补码表示-1的能力20202题2分2.67%移码…...
剖析提示词工程中的递归提示
递归提示:解码AI交互的本质,构建复杂推理链 递归提示的核心思想,正如示例所示,是将一个复杂任务分解为一系列更小、更易于管理、逻辑上前后关联的子任务。每个子任务由一个独立的提示来驱动,而前一个提示的输出(经过必要的解析和转换)则成为下一个提示的关键输入。这种…...
【SSL证书系列】https双向认证中客户端认证的原理
HTTPS双向认证(也称为双向SSL/TLS认证)是一种增强安全性的机制,其中客户端和服务器都需要验证彼此的数字证书,以确保双方身份的真实性。以下是其核心原理和步骤的详细解析: 一、双向认证的核心目标 双向身份验证&#…...