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

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...