当前位置: 首页 > 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)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗茶,…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...