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

C++学习:二分查找

二分查找的前提

库函数只能对数组进行二分查找。
对一个数组进行二分查找的前提是这个数组中的元素是单调的。
一般为单调不减,当然如果是单调不增也可以(需要修改比较函数)

例如:
[1,5,5,9,18]是单调的

[1 , 9, 9, 7, 15]不是单调的

[9,8,8,7,7,1]是单调的

binary_search函数

binary_search是C++标准库中的一个算法函数,用于在已排序的序列(例如数组或容器vector)中查找特定元素。

它通过二分查找算法来确定序列中是否存在目标元素。

函数返回一个bool值,表示目标元素是否存在于序列中。

如果需要获取找到的元素的位置,可以使用std::lower_bound函数或std::upper_bound函数。

vector <int> numbers = {1, 3, 5 , 7 ,9};int target = 5;bool found = binary_search(number.begin(),number.end(),target);if(found){cout << "Target element" << target << "found." << endl;
}else{cout << "Target element" << target << "not found." << endl;
}

lower_bound和upper_bound

前提:数组必须为非降序

如果要在非升序的数组中使用,可以通过修改比较函数实现(方法与sort自定义比较函数类似)

lower_bound(st,ed,_x)返回地址[st, ed)中第一个大于等于x的元素的地址

upper_bound(st,ed,x)返回地址[st,ed)中第一个大于x的元素的地址

如果不存在则返回最后一个元素的下一个位置,在vector中即end()

地址-首地址=下标

[lower_bound , upper_bound)

//初始化
vector <int> v={5,1,7,3,10,18,9};
//排序
sort(v.begin(),v.end());
for(auto &i : v)cout<< i<<'cout<<'\n';
//找到数组中第一个大于等于8的元素的位置
cout<<(lower_bound(v.begin(),v.end(),8)- v.begin())<<'\n';

例题:

#include <bits/stdc++.h>
using namespace std;
int main(void)
{int data[200];for(int i = 0 ; i < 200 ; i ++)data[i] = 4 * i + 6;int target  = 0;cin >> target;cout << (lower_bound(data,data+200,target)- data);return 0;
}

相关文章:

C++学习:二分查找

二分查找的前提 库函数只能对数组进行二分查找。 对一个数组进行二分查找的前提是这个数组中的元素是单调的。 一般为单调不减&#xff0c;当然如果是单调不增也可以(需要修改比较函数) 例如: [1&#xff0c;5&#xff0c;5&#xff0c;9&#xff0c;18]是单调的 [1 , 9, 9,…...

语言与科技创新(大语言模型对科技创新的影响)

1.语言因素对科技创新的影响 科技创新中的语言因素至关重要&#xff0c;具体体现在以下几个方面&#xff1a; 科技文献交流&#xff1a; 英语作为全球科学研究的通用语言&#xff0c;极大地推动了科技成果的国际传播与合作。在国际上&#xff0c;科学家们在发表论文、报告研究…...

【C语言】简单贪吃蛇实现保姆级教学!!!

关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა 新年快乐呀小伙伴 引言&#xff1a; 小伙伴们应该都有一个做游戏的梦吧&#xff1f;今天让小庄来用C语言简单实现一下我们的童年邪典贪吃蛇&#xff0c;顺便巩固我们的C语言知识&#xff0c;请安心食用~ 文章目录 贪吃蛇效果一.游戏前工作…...

rtt设备io框架面向对象学习-uart设备

目录 1.uart设备基类2.uart设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 1.uart设备基类 此层处于设备驱动框架层。也是抽象类。 在/ components / drivers / include / drivers 下的serial.h定义了如下uart设备基类 struc…...

Innodb下修改事务工作流程(buffer pool、redo log、undolog)

1、在Buffer Pool中读取数据&#xff1a;当InnoDB需要更新一条记录时&#xff0c;首先会在Buffer Pool中查找该记录是否在内存中。如果没有在内存中&#xff0c;则从磁盘读取该页到Buffer Pool中。 2、记录UndoLog&#xff1a;在修改操作前&#xff0c;InnoDB会在Undo Log中记…...

redis为什么使用跳跃表而不是树

Redis中支持五种数据类型中有序集合Sorted Set的底层数据结构使用的跳跃表&#xff0c;为何不使用其他的如平衡二叉树、b树等数据结构呢&#xff1f; 1&#xff0c;redis的设计目标、性能需求&#xff1a; redis是高性能的非关系型&#xff08;NoSQL&#xff09;内存键值数据…...

【matalab】基于Octave的信号处理与滤波分析案例

一、基于Octave的信号处理与滤波分析案例 GNU Octave是一款开源软件&#xff0c;类似于MATLAB&#xff0c;广泛用于数值计算和信号处理。 一个简单的信号处理与滤波分析案例&#xff0c;说明如何在Octave中生成一个有噪声的信号&#xff0c;并设计一个滤波器来去除噪声。 首…...

Elasticsearch:特定领域的生成式 AI - 预训练、微调和 RAG

作者&#xff1a;来自 Elastic Steve Dodson 有多种策略可以将特定领域的知识添加到大型语言模型 (LLM) 中&#xff0c;并且作为积极研究领域的一部分&#xff0c;正在研究更多方法。 对特定领域数据集进行预训练和微调等方法使 LLMs 能够推理并生成特定领域语言。 然而&#…...

HarmonyOS—UI 开发性能提升的推荐方法

开发者若使用低性能的代码实现功能场景可能不会影响应用的正常运行&#xff0c;但却会对应用的性能造成负面影响。本章节列举出了一些可提升性能的场景供开发者参考&#xff0c;以避免应用实现上带来的性能劣化。 使用数据懒加载 开发者在使用长列表时&#xff0c;如果直接采用…...

84 CTF夺旗-PHP弱类型异或取反序列化RCE

目录 案例1&#xff1a;PHP-相关总结知识点-后期复现案例2&#xff1a;PHP-弱类型对比绕过测试-常考点案例3&#xff1a;PHP-正则preg_match绕过-常考点案例4&#xff1a;PHP-命令执行RCE变异绕过-常考点案例5&#xff1a;PHP-反序列化考题分析构造复现-常考点涉及资源&#xf…...

Duilib List 控件学习

这是自带的一个示例; 一开始运行的时候List中是空的,点击Search按钮以后就填充列表框; 先看一下列表框列头是在xml文件中形成的; <List name="domainlist" bkcolor="#FFFFFFFF" ... menu="true"> <ListHeader height="24…...

详细了解Node.js的配置与使用!

详细了解Node.js的配置与使用&#xff01; Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。它允许开发者在服务器端运行 JavaScript&#xff0c;从而实现全栈 JavaScript 开发。本文将介绍 Node.js 的配置和 npm 的应用。 一、Node.js 配置 下载与安装 首先&…...

OpenCV 移动最小二乘图像变形

文章目录 一、简介二、实现代码三、实现效果参考文献一、简介 在现实生活中,我们常常应用一些刚性的变换来实现物体的旋转平移,对于非刚性的变换我们都没有在意,其实这种变换也是无处不在的,如我们经常看的动画就可以通过一些非刚性的变换达到一些非常夸张的效果。这里,我…...

【深度学习】S2 数学基础 P4 概率论

目录 基本概率论概率论公理随机变量 多个随机变量联合概率条件概率贝叶斯定理求和法则独立性 期望与方差小结 基本概率论 机器学习本质上&#xff0c;就是做出预测。而概率论提供了一种量化和表达不确定性水平的方法&#xff0c;可以帮助我们量化对某个结果的确定性程度。 在…...

跟我学c++中级篇——静态多态

一、多态 Polymorphism&#xff0c;多态。学习过c的人如果不知道多态&#xff0c;基本上就是打入c内部的C程序员了。在前边曾经对多态进行过分析&#xff0c;对其中的虚函数&#xff08;虚表等&#xff09;也进行过较为详细的说明。 多态其实非常好理解&#xff0c;不要硬扣书…...

设计模式--桥接模式(Bridge Pattern)

桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式&#xff0c;它主要是用于将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。 桥接模式主要包含以下几个角色&#xff1a; Abstraction&#xff08;抽象类&#xff09;&#xff1a;定义抽象类的…...

统计图饼图绘制方法(C语言)

统计图饼图绘制方法&#xff08;C语言&#xff09; 常用的统计图有条形图、柱形图、折线图、曲线图、饼图、环形图、扇形图。 前几类图比较容易绘制&#xff0c;饼图绘制较难。今值此介绍饼图的绘制方法。 本方法采用C语言的最基本功能&#xff1a; &#xff08; 1.&#xff09…...

洛谷C++简单题小练习day12—寻找最小值小程序

day12--寻找最小值--2.16 习题概述 题目描述 给出 n 和 n 个整数 ai​&#xff0c;求这 n 个整数中最小值是什么。 输入格式 第一行输入一个正整数 n&#xff0c;表示数字个数。 第二行输入 n 个非负整数&#xff0c;表示 1,2…a1​,a2​…an​&#xff0c;以空格隔开。 …...

相机图像质量研究(13)常见问题总结:光学结构对成像的影响--鬼影

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

车载诊断协议DoIP系列 —— 车辆以太网节点需求汇总

车载诊断协议DoIP系列 —— 车辆以太网节点需求汇总 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗茶,…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

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

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

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...