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

二分查找算法的全面解析C++

一、核心原理与特性

二分查找是一种**对数时间复杂度(O(log n))**的高效搜索算法46,需满足两个前提条件:

  1. 数据存储在连续内存空间(如数组)
  2. 数据按升序/降序有序排列35

算法通过折半比较缩小搜索范围:

  • 初始化左右边界left=0right=length-1
  • 计算中间位置mid = left + (right - left)/2(避免整数溢出)
  • 比较arr[mid]与目标值,调整左右边界18

二、标准实现步骤(C++迭代版)

Cpp

int binarySearch(int arr[], int size, int target) { int left = 0, right = size - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; // 未找到 }

关键点

  • 循环终止条件left <= right确保完整搜索区间覆盖48
  • 边界调整时mid±1避免死循环4

三、边界处理进阶

1. 查找第一个/最后一个匹配项

Cpp

// 查找第一个等于target的位置 int findFirst(int arr[], int size, int target) { int left = 0, right = size - 1, res = -1; while (left <= right) { int mid = left + (right - left)/2; if (arr[mid] >= target) { right = mid - 1; if (arr[mid] == target) res = mid; } else { left = mid + 1; } } return res; }

此变体通过记录临时结果处理重复元素26

2. 旋转数组查找

适用于部分有序数组(如[4,5,6,7,0,1,2]):

  • 通过比较arr[mid]与左右边界判断有序区间
  • 调整搜索方向至目标可能存在的区域76

四、应用场景与优化

场景类型适用案例优化策略
精确匹配有序数组元素定位标准二分法
范围查找统计成绩分布、查找IP归属地边界变体(lower/upper_bound)
数学问题转化求平方根、寻找峰值调整比较条件
工程实践数据库索引、缓存查找结合跳表等数据结构

五、调试工具推荐

  1. Valgrind:检测内存越界问题1
  2. 边界测试用例
    • 目标为第一个/最后一个元素
    • 数组中全为相同元素
    • 空数组或单元素数组

完整代码实现和进阶案例可参考146中的项目实例。当处理动态数据集时,建议结合平衡二叉搜索树(STL中的set/map)实现高效插入与查找。

相关文章:

二分查找算法的全面解析C++

一、核心原理与特性 二分查找是一种**对数时间复杂度(O(log n))**的高效搜索算法46&#xff0c;需满足两个前提条件&#xff1a; 数据存储在连续内存空间&#xff08;如数组&#xff09;数据按升序/降序有序排列35 算法通过折半比较缩小搜索范围&#xff1a; 初始化左右边界…...

深度学习(5)-卷积神经网络

我们将深入理解卷积神经网络的原理&#xff0c;以及它为什么在计算机视觉任务上如此成功。我们先来看一个简单的卷积神经网络示例&#xff0c;它用干对 MNIST数字进行分类。这个任务在第2章用密集连接网络做过&#xff0c;当时的测试精度约为 97.8%。虽然这个卷积神经网络很简单…...

第9章:LangChain结构化输出-示例3(日期和时间提取服务)

如何使用LangChain4j框架创建和使用多种AI服务。它通过定义接口和注解,将自然语言处理任务(如情感分析、数字提取、日期提取、POJO提取等)封装为服务,并通过LangChain4j的AiServices动态生成这些服务的实现。 本章主要讲述基于LangChain调用大模型如何进行结构化输出的真实…...

解决Open WebU无法显示基于OpenAI API接口的推理内容的问题

解决方案 把reasoning content的东西移到content中来 并在reasoning时&#xff0c;手动加上标签。具体做法是截获第三方api返回的stream&#xff0c;并修改其中的内容&#xff0c;再移交给open webUI处理。 在backend\open_webui\routers\openai.py中 找到 generate_chat_com…...

AI颠覆蛋白质工程:ProMEP零样本预测突变效应

概述 在生命科学的“造物革命”中&#xff0c;蛋白质工程一直面临着“试错成本”与“设计效率”的双重挑战——传统方法依赖繁复的多序列比对&#xff08;MSA&#xff09;或耗时的实验室筛选&#xff0c;如同在浩瀚的蛋白质宇宙中盲选星辰。而今日&#xff0c;一项发表于《Cel…...

QT闲记-状态栏,模态对话框,非模态对话框

1、创建状态栏 跟菜单栏一样,如果是继承于QMainWindow类,那么可以获取窗口的状态栏,否则就要创建一个状态栏。通过statusBar()获取窗口的状态栏。 2、添加组件 通常添加Label 来显示相关信息,当然也可以添加其他的组件。通过addWidget()添加组件 3、设置状态栏样式 …...

QQ登录测试用例报告

QQ登录测试用例思维导图 一、安全性测试用例 1. 加密传输与存储验证 测试场景&#xff1a;输入账号密码并提交登录请求。预期结果&#xff1a;账号密码通过加密传输&#xff08;如HTTPS&#xff09;与存储&#xff08;如哈希加盐&#xff09;&#xff0c;无明文暴露。 2. 二…...

ipad连接电脑断断续续,不断弹窗的解决办法

因为ipad air 屏幕摔坏&#xff0c;换了一个内外屏&#xff0c;想用爱思检验一下屏幕真伪&#xff0c; 连接电脑时&#xff0c;断断续续&#xff0c;连上几秒钟然后就断开&#xff0c;然后又连上 然后又断开&#xff0c;不断地弹出信任的弹窗。 刚开始以为是数据线问题&#x…...

《FFTformer:基于频域的高效Transformer用于高质量图像去模糊》

paper&#xff1a;2211.12250 GitHub&#xff1a;kkkls/FFTformer: [CVPR 2023] Effcient Frequence Domain-based Transformer for High-Quality Image Deblurring CVPR 2023 目录 摘要 1、介绍 2、相关工作 2.1 基于深度CNN的图像去模糊方法 2.2 Transformer及其在图…...

std::call_once

std::call_once 是 C11 标准库中提供的一个线程安全的一次性调用机制&#xff0c;位于 <mutex> 头文件中。它用于确保在多线程环境中&#xff0c;某个函数&#xff08;或可调用对象&#xff09;仅被调用一次&#xff0c;无论有多少线程尝试调用它。这种机制常用于实现线程…...

网络安全研究

1.1 网络安全面临的威胁 网络安全面临的威胁呈现出多样化和复杂化的趋势&#xff0c;给个人、企业和国家的安全带来了严峻挑战。以下是当前网络安全面临的主要威胁&#xff1a; 1.1.1 数据泄露风险 数据泄露是当前网络安全的重大威胁之一。根据国家互联网应急中心发布的《20…...

【软考网工】华为交换机命令

目录 1、华为交换机命令行的三种视图2、修改交换机名称3、关闭和开启信息中心4、vlan附录&#xff1a; 交换机型号&#xff1a;S5700 1、华为交换机命令行的三种视图 <Huaweu> #用户视图。特征&#xff1a;尖括号、用户名。 [Huawei] #系统视图。特…...

【行业解决方案篇十八】【DeepSeek航空航天:故障诊断专家系统 】

引言:为什么说这是“航天故障终结者”? 2025年春节刚过,航天宏图突然官宣"DeepSeek已在天权智能体上线",这个搭载在卫星和空间站上的神秘系统,号称能提前48小时预判99.97%的航天器故障。这不禁让人想起年初NASA禁用DeepSeek引发的轩然大波,更让人好奇:这套系…...

输入菜单关键字,遍历匹配到 menuIds,展开 匹配节点 的所有父节点以及 匹配节点 本身,高亮 匹配节点

菜单检索&#xff0c;名称、地址、权限标志 等 关键字匹配、展开、高亮(全程借助 DeepSeek ) 便捷简洁的企业官网 的后台菜单管理&#xff0c;图示&#xff1a; 改造点&#xff1a; &#xff08;1&#xff09;修改 bootstrapTreeTable 的节点class命名方式为&#xff1a;treeg…...

【Blender】二、建模篇--07,置换修改器

0 00:00:03,620 --> 00:00:08,620 大家好 这张课呢 我们来讲建模篇的最后一个重点修改器 置换修改器 1 00:00:08,980 --> 00:00:17,580 把它放在最后 不是因为它最难 而是因为它很常用 尤其大家以后做材质的时候 我们可以用一张贴图把一个平面做出来凹凸的感觉 2 00:00…...

玩转 Java 与 Python 交互,JEP 库来助力

文章目录 玩转 Java 与 Python 交互&#xff0c;JEP 库来助力一、背景介绍二、JEP 库是什么&#xff1f;三、如何安装 JEP 库&#xff1f;四、JEP 库的简单使用方法五、JEP 库的实际应用场景场景 1&#xff1a;数据处理场景 2&#xff1a;机器学习场景 3&#xff1a;科学计算场…...

鸿蒙学习-

鸿蒙数据传值 //* 传值 //* State /**State创建一个响应式的数据&#xff0c;但不是所有的更改都会引起刷新&#xff0c;只有被框架观察到的修改才会被刷新UI* 1. 基本数据类型如 number string boolean等值的变化修改* 2. Object类型&#xff0c;只会观察到第一层的数据变化或…...

list结构刨析与模拟实现

目录 1.引言 2.C模拟实现 2.1模拟实现结点 2.2模拟实现list前序 1&#xff09;构造函数 2&#xff09;push_back函数 2.3模拟实现迭代器 1&#xff09;iterator 构造函数和析构函数&#xff1a; *操作符重载函数&#xff1a; 前置/后置/--&#xff1a; /!操作符重载…...

机器人部分专业课

华东理工 人工智能与机器人导论 Introduction of Artificial Intelligence and Robots 必修 考查 0.5 8 8 0 1 16477012 程序设计基础 The Fundamentals of Programming 必修 考试 3 64 32 32 1 47450012 算法与数据结构 Algorithm and Data Structure 必修 考试 3 56 40 …...

流行粗野主义几何风现代曲线标题logo设计psai无衬线英文字体安装包 Mortend – Extended Family

介绍我们名为 Mortend 的新探索&#xff0c;这是一个强大的扩展字体系列。Mortend 的设计具有几何形状、大胆、强烈的曲线和现代感。灵感来自当今流行的粗野主义海报和极简主义设计&#xff0c;让您有更多机会表达您的创造力。这个字体系列带来了强烈的感觉而优雅的外观&#x…...

终极Windows文件搜索革命:EverythingToolbar高级功能完全指南

终极Windows文件搜索革命&#xff1a;EverythingToolbar高级功能完全指南 【免费下载链接】EverythingToolbar Everything integration for the Windows taskbar. 项目地址: https://gitcode.com/gh_mirrors/eve/EverythingToolbar 还在为Windows自带的缓慢搜索功能而烦…...

OpenHarmony:Docker编译环境参考资料

OpenHarmony的Docker编译环境&#xff0c;可以参考如下官网&#xff1a; https://gitee.com/openharmony/docs/blob/master/zh-cn/device-dev/get-code/gettools-acquire.md...

从老古董NE555到单片机:手把手教你做一个简易数字频率计(STC89C52)

从NE555到STC89C52&#xff1a;打造高性价比数字频率计的完整指南 在电子爱好者的世界里&#xff0c;测量信号频率是一项基础却至关重要的技能。想象一下&#xff0c;当你调试一个振荡电路时&#xff0c;能够实时看到信号频率的变化&#xff1b;或者当你需要验证一个传感器输出…...

告别理论!用Minitab实战拆解CPK与PPK:从公式差异到实际生产报告解读

告别理论&#xff01;用Minitab实战拆解CPK与PPK&#xff1a;从公式差异到实际生产报告解读 在工厂车间的日常质量管理中&#xff0c;CPK和PPK这两个指标常常让质量工程师们又爱又恨。爱的是它们能直观反映生产过程能力&#xff0c;恨的是当面对一份满是数字的报告时&#xff0…...

用Python给图片藏个小秘密:手把手教你实现LSB隐写术(附完整代码)

用Python给图片藏个小秘密&#xff1a;手把手教你实现LSB隐写术&#xff08;附完整代码&#xff09; 你是否想过在朋友圈分享的照片里藏一段悄悄话&#xff1f;或是把重要信息伪装成普通图片&#xff1f;这听起来像间谍电影里的情节&#xff0c;但用Python只需几十行代码就能实…...

网安局紧急预警:“银狐病毒” 全国高发,专偷银行卡与验证码,你的手机可能已被控制

近期&#xff0c;全国多地网安部门、国家计算机病毒应急处理中心接连发布风险通报&#xff1a;“银狐病毒” 木马家族进入新一轮高发期&#xff0c;通过短信、社交群、伪装软件疯狂传播&#xff0c;已造成大量用户资金被盗、隐私泄露&#xff0c;成为当前威胁百姓 “钱袋子” 的…...

终极指南:如何通过智能鼠标宏配置解锁PUBG精准射击的完整潜力

终极指南&#xff1a;如何通过智能鼠标宏配置解锁PUBG精准射击的完整潜力 【免费下载链接】logitech-pubg PUBG no recoil script for Logitech gaming mouse / 绝地求生 罗技 鼠标宏 项目地址: https://gitcode.com/gh_mirrors/lo/logitech-pubg 你是否在《绝地求生》的…...

8大主流网盘直链下载助手:免费获取真实下载链接的完整指南

8大主流网盘直链下载助手&#xff1a;免费获取真实下载链接的完整指南 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / …...

Rust Trait 系统设计原则

Rust Trait系统设计原则&#xff1a;构建灵活与安全的抽象 Rust作为一门注重安全与性能的系统级语言&#xff0c;其Trait系统是类型抽象和多态的核心机制。Trait不仅定义了类型的行为契约&#xff0c;还通过零成本抽象和编译期检查&#xff0c;为开发者提供了强大的表达能力。…...

从数据到生物学故事:手把手教你用ATAC-seq+RNA-seq做整合分析

从数据到生物学故事&#xff1a;ATAC-seq与RNA-seq整合分析实战指南 当我们在显微镜下观察肝细胞和神经细胞时&#xff0c;尽管它们拥有完全相同的DNA序列&#xff0c;却展现出截然不同的形态和功能。这种差异的核心秘密隐藏在染色质的动态开放与闭合之中。ATAC-seq技术就像一把…...