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

STL二分查找

本课主要介绍容器部分里面的二分查找函数。涉及的函数有 3 个,这 3 个函数的强两个输入参数都和迭代器有关,或者说参数是可以迭代的,而第三个参数则是你要查找的值。

binary_search 的返回结果是 bool 值,如果找得到,就返回 true,找不到,就返回 false。

我们抛开那些很玄乎的术语,直接上代码。先用一个普通数组作为例子。

int x[1001],n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i];sort(x+1,x+1+n); // 排序,数组必须要有序,binary_search 是不负责排序的int t;
while(m--){ // 表示有 m 次查询cin>>t;if(binary_search(x+1,x+1+n,t))printf("找得到数字 %d\n",t);elseprintf("找不到数字 %d\n",t);
}

 

第二个例子是基于vector的二分查找。上面的例子做个平移吧,逻辑不变。

vector <int> x;
int n,m;
cin>>n>>m;
int t;
for(int i=1;i<=n;i++){cin>>t;x.push_back();
}sort(x.begin(),x.end()); // 排序,数组必须要有序,binary_search 是不负责排序的while(m--){ // 表示有 m 次查询cin>>t;if(binary_search(x.begin(),x.end(),t))printf("找得到数字 %d\n",t);elseprintf("找不到数字 %d\n",t);
}

 

binary_search 的前两个参数还可以是指向 vector 元素的迭代器,那么就是在这两个迭代器范围内查找了。

2. lower_bound

lower_bound 函数输入的参数和 binary_search 类似,只不过,它返回的是第一个大于等于查找值的地址(迭代器)。如果找不到,返回的是第二个输入参数的指针,记住,还是左闭右开原则。

int x[1001],n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i];sort(x+1,x+1+n); // 排序,数组必须要有序,binary_search 是不负责排序的int t;
int *p;
while(m--){ // 表示有 m 次查询cin>>t;p = lower_bound(x+1,x+1+n,t)if(p!=x+1+n)printf("数组中第一个大于等于 %d 的数的下标是 %d\n",t,p-x);elseprintf("找不到数字 %d\n",t);
}

 

如果是针对 vector,上述的代码要改成

vector <int> x;
int n,m;
cin>>n>>m;int t;
for(int i=1;i<=n;i++){cin>>t;x.push_back(t);
}sort(x.begin(),x.end()); // 排序,数组必须要有序,binary_search 是不负责排序的vector <int>:: iterator it;
while(m--){ // 表示有 m 次查询cin>>t;it = lower_bound(x.begin(),x.end(),t)if(it!=x.end())printf("动态数组中第一个大于等于 %d 的数的下标是 %d\n",t, it-x.begin());elseprintf("动态数组中找不到数字 %d\n",t);
}

 

3. upper_bound

upper_bound 和 lower_bound 非常类似,区别是函数返回的是第一个大于查找值的地址(迭代器)。

4. 重要补充说明

  1. 对于 set 和 map 来说,有成员函数 upper_bound 和 lower_bound 的,所以,不应该用外面的的那个 upper_bound 和 lower_bound。
map <string ,int> m;
int n,t;
cin>>n;
string a;
for(int i=1;i<=n;i++){cin>>a>>t;m[a] = t;
}map <string ,int>::iterator it;
//it = lower_bound(m.begin(),m.end(),"123"); // 这是错误的 
it = m.lower_bound("123"); // 这是正确的
cout<<it->first<<" "<<it->second;
}

 

对于 set 容器,可以用外面的 lower_bound 和 upper_bound,但是效率上远远没有自己的成员函数快。

set <string> s;
int n;
cin>>n;
string a;
for(int i=1;i<=n;i++){cin>>a;s.insert(a);
}set <string>::iterator it;
//it = lower_bound(s.begin(),s.end(),"123"); //语法上这句也是可以的,但是效率比较低
it = s.lower_bound("123"); //这是正确的,会快很多
cout<<*it;}

 

  1. 上面的 3 个二分查找函数都需要用到 运算符 < 。如果你的数组、动态数组存放的是结构体变量,记得要定义 < 运算符。

  2. 定义< 运算符 的时候,要用上 const 关键字和采用 引用传参 。这是 STL 模板套用的时候需要的,否则 upper_bound 函数会出错的。

const 关键字的意思是传进去的参数是不能被修改的,只能读,不能改。引用传参意思是形参和实参是一样。表面看,这很矛盾,既然你都不打算修改参数的值了,为什么还要采用 引用传参 呢。引用传参 的好处是数据不用被复制一遍,提高了效率。你定义函数的时候加上const 关键字和采用 引用传参没有任何坏处,别的模板套用你的运算符函数的时候,一定能套得上。

下面举个例子,演示怎么加上 const 关键字 和 引用传参

struct Point{int x,y;//横坐标和纵坐标bool operator < (const Point& other) const{return x<other.x||(x==other.x&&y<other.y);}// 左边的 const 表示传进去的参数 other 不能修改// 右边的 const 表示它自己不能修改(仅仅是执行 < 的过程中不能修改) 
};

 

第二种,就是把运算符写在结构体外面的写法了

struct Point{int x,y;//横坐标和纵坐标
};
bool operator < (const Point& i,const Point& j){return i.x<j.x||(i.x==j.x&&i.y<j.y);
};

相关文章:

STL二分查找

本课主要介绍容器部分里面的二分查找函数。涉及的函数有 3 个&#xff0c;这 3 个函数的强两个输入参数都和迭代器有关&#xff0c;或者说参数是可以迭代的&#xff0c;而第三个参数则是你要查找的值。 1. binary_search binary_search 的返回结果是 bool 值&#xff0c;如果找…...

啤酒游戏—企业经营决策沙盘

感谢黄浦区文华学院的邀请&#xff0c;今年是为南房集团开展系统思考培训的第二年。我们现在为客户设计的一整年系统思考训练中&#xff0c;会将系统环路结构图与真实议题研讨作为前置内容&#xff0c;让大家在理解整体框架后&#xff0c;再体验麻省理工学院系统动力学著名的“…...

尚硅谷-react教程-求和案例-@redux-devtools/extension 开发者工具使用-笔记

## 7.求和案例_react-redux开发者工具的使用(1).npm install redux-devtools/extension(2).store中进行配置import { composeWithDevTools } from redux-devtools/extension;export default createStore(allReducer,composeWithDevTools(applyMiddleware(thunk))) src/redux/s…...

【动手学强化学习】part2-动态规划算法

阐述、总结【动手学强化学习】章节内容的学习情况&#xff0c;复现并理解代码。 文章目录 一、什么是动态规划&#xff1f;1.1概念1.2适用条件 二、算法示例2.1问题建模2.2策略迭代&#xff08;policyiteration&#xff09;算法2.2.1伪代码2.2.2完整代码2.2.3运行结果2.2.4代码…...

【python爬虫实战】爬取全年天气数据并做数据可视化分析!附源码

由于篇幅限制&#xff0c;无法展示完整代码&#xff0c;需要的朋友可在下方获取&#xff01;100%免费。 一、主题式网络爬虫设计方案 1. 主题式网络爬虫名称&#xff1a;天气预报爬取数据与可视化数据 2. 主题式网络爬虫爬取的内容与数据特征分析&#xff1a; - 爬取内容&am…...

初识Linux · 动静态库(incomplete)

目录 前言&#xff1a; 静态库 动态库 前言&#xff1a; 继上文&#xff0c;我们从磁盘的理解&#xff0c;到了文件系统框架的基本搭建&#xff0c;再到软硬链接部分&#xff0c;我们开始逐渐理解了为什么运行程序需要./a.out了&#xff0c;这个前面的.是什么我们也知道了。…...

华为OD机试 - 匿名信(Java 2024 E卷 100分)

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;E卷D卷A卷B卷C卷&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;私信哪吒&#xff0c;备注华为OD&#xff0c;加…...

通过rancher2.7管理k8s1.24及1.24以上版本的k8s集群

目录 初始化实验环境 安装Rancher 登录Rancher平台 通过Rancher2.7管理已存在的k8s最新版集群 文档中的YAML文件配置直接复制粘贴可能存在格式错误&#xff0c;故实验中所需要的YAML文件以及本地包均打包至网盘. 链接&#xff1a;https://pan.baidu.com/s/1oYX4eGoBtW_R-7i…...

text-align的属性justify

text-align常用的属性是left、center、right&#xff0c;具体的可参考css解释&#xff0c;今天重点记录的对象是justify justify 可以使文本的两端都对齐在两端对齐文本中&#xff0c;文本行的左右两端都放在父元素的内边界上。然后&#xff0c;调整单词和字母间的间隔&#x…...

使用python自制桌面宠物,好玩!——枫原万叶桌宠,可以直接打包成exe去跟朋友炫耀。。。

大家好&#xff0c;我是小黄。 今天我们使用python实现一个桌面宠物。只需要gif动态图片就行。超级简单容易上手。 #完整源代码可在下方图片免费获取 一&#xff1a;下载相关的库文件。 我们本次使用到的库文件为&#xff1a;tkinter和pyautogui 下载命令&#xff1a; pip…...

使用 ASP.NET Core 8.0 创建最小 API

构建最小 API&#xff0c;以创建具有最小依赖项的 HTTP API。 它们非常适合需要在 ASP.NET Core 中仅包括最少文件、功能和依赖项的微服务和应用。 本教程介绍使用 ASP.NET Core 生成最小 API 的基础知识。 在 ASP.NET Core 中创建 API 的另一种方法是使用控制器。 有关在最小 …...

气候服务平台ClimateSERV2.0简介(python)

1 简介 ClimateSERV 2.0允许开发从业者、科学家/研究人员和政府决策者可视化和下载历史降雨数据、植被状况数据以及 180 天的降雨和温度预报&#xff0c;以增进对农业和水资源供应相关问题的理解并做出改进的决策。 这些数据可以通过 Web 应用程序直接访问&#xff0c;也可以…...

Docker | centos7上对docker进行安装和配置

安装docker docker配置条件安装地址安装步骤2. 卸载旧版本3. yum 安装gcc相关4. 安装需要的软件包5. 设置stable镜像仓库6. 更新yum软件包索引7. 安装docker引擎8. 启动测试9. 测试补充&#xff1a;设置国内docker仓库镜像 10. 卸载 centos7安装docker https://docs.docker.com…...

React--》掌握Valtio让状态管理变得轻松优雅

Valtio采用了代理模式&#xff0c;使状态管理变得更加直观和易于使用&#xff0c;同时能够与React等框架无缝集成&#xff0c;本文将深入探讨Valtio的核心概念、使用场景以及其在提升应用性能中的重要作用&#xff0c;帮助你掌握这一强大工具&#xff0c;从而提升开发效率和用户…...

python爬虫百度图片

直接给代码&#xff0c;可直接用&#xff0c;个人需要修改的地方有两处&#xff1a; self.directory 这是本地存储地址&#xff0c;修改为自己电脑的地址&#xff0c;另外&#xff0c;**{}**不要删spider.json_count 10 这是下载的图像组数&#xff0c;一组有30张图像&#x…...

前端开发:Vue中数据绑定原理

Vue 中最大的一个特征就是数据的双向绑定&#xff0c;而这种双向绑定的形式&#xff0c;一方面表现在元数据与衍生数据之间的响应&#xff0c;另一方面表现在元数据与视图之间的响应&#xff0c;而这些响应的实现方式&#xff0c;依赖的是数据链&#xff0c;因此&#xff0c;要…...

CTF-RE 从0到N: TEA

TEA TEA&#xff08;Tiny Encryption Algorithm&#xff0c;轻量加密算法&#xff09; 是一种简单、快速的对称加密算法。它是一个分组加密算法&#xff0c;通常用于加密 64 位的数据块&#xff0c;并使用 128 位的密钥。TEA 是一种“费斯妥结构”&#xff08;Feistel structu…...

python 使用PIL获取图片长宽

在Python中&#xff0c;你可以使用Pillow库&#xff08;PIL的一个分支和替代品&#xff09;来获取图片的长和宽。Pillow提供了丰富的图像处理功能&#xff0c;包括获取图像的基本属性&#xff0c;如尺寸。 以下是一个简单的示例&#xff0c;展示了如何使用Pillow库来获取图片的…...

【Nas】X-DOC:搞机之PVE部署All In One(黑群晖NAS 软路由OpenWrt Docker Win10远程桌面)

【Nas】X-DOC&#xff1a;搞机之PVE部署All In One&#xff08;黑群晖NAS & 软路由OpenWrt & Docker & Win10远程桌面&#xff09; 1、原硬件配置清单&#xff1a;2、改AIO后增加配置清单&#xff1a;3、虚拟化平台PVE&#xff1a;4、搭建的关键服务&#xff1a; 1…...

linux 驱动源码分析的理解。

首先 &#xff0c; 是&#xff4c;&#xff49;&#xff4e;&#xff55;&#xff58; 驱动&#xff0c;我看网上的老师&#xff0c;在分析源码时 &#xff0c; 不会 所有的函数都分析&#xff0c;而是分析一些比较重要的函数&#xff0c;一些厉害的人&#xff0c;在分析源码时…...

鸿蒙-任务栏右击退出 或 UIAbility窗口关闭,怎么弹框拦截

onPrepareToTerminate 需要配置权限 ohos.permission.PREPARE_APP_TERMINATE 参考链接&#xff1a;文档中心import { emitter } from kit.BasicServicesKit; import { common } from kit.AbilityKit; import { TipsDialog } from kit.ArkUI;// entryAbility.ets 在你的uiabilit…...

【C++进阶篇】——STL的简介

【C进阶篇】——STL的简介 1.什么是STL STL(standard template libaray-标准模板库)&#xff1a;是C标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且是一个包罗数据结构与算法的软件框架。 2.STL的版本 原始版本 Alexander Stepanov、Meng Lee 在…...

信息安全工程师(70)网络攻击陷阱技术与应用

前言 网络攻击陷阱技术是一种主动的防御方法&#xff0c;作为网络安全的重要策略和技术手段&#xff0c;有利于网络安全管理者获得信息优势。 一、网络攻击陷阱技术原理 网络攻击陷阱技术可以消耗攻击者所拥有的资源&#xff0c;加重攻击者的工作量&#xff0c;迷惑攻击者&…...

Web保存状态的手段(Session的使用)

一&#xff0c;JSP中的page指令 1. <% page language“java” session“true”%> session&#xff1a;此页面是否使用session&#xff0c;默认值为true 二&#xff0c;使用Session完善之前的登录程序 1. 如何禁止直接输入URL地址进入登录功能的欢迎界面&#xff1f; …...

第五十四章 安全元素的详细信息 - DerivedKeyToken 详情

文章目录 第五十四章 安全元素的详细信息 - <DerivedKeyToken> 详情详情消息中的位置 第五十四章 安全元素的详细信息 - 详情 <DerivedKeyToken> 的目的是携带发送者和接收者可以独立使用的信息来生成相同的对称密钥。这些方可以使用该对称密钥对 SOAP 消息的相关…...

kafka 的高可用机制是什么?

大家好&#xff0c;我是锋哥。今天分享关于【kafka 的高可用机制是什么&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; kafka 的高可用机制是什么&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Apache Kafka 是一个分布式消息系统&am…...

4.1.3 网站通信技术

文章目录 1. 网站通信方式2. URL - 统一资源定位符定义格式演示 3. 发送请求的4种形式在地址栏中输入URL访问超链接href属性指定URLform表单在action中指定URL通过AJAX请求后端数据 4. 两种不同返回的请求发送URL&#xff0c;后端处理完响应页面发送AJAX请求&#xff0c;后端处…...

Java-图书管理系统

我的个人主页 欢迎来到我的Java图书管理系统&#xff0c;接下来让我们一同探索如何书写图书管理系统吧&#xff01; 1管理端和用户端 2建立相关的三个包&#xff08;book、operation、user&#xff09; 3建立程序入口Main类 4程序运行 1.首先图书馆管理系统分为管理员端和…...

python如何通过json以及pickle读写保存数据

记录信息 比如说我写了这样一段程序&#xff0c;记录了爱吃的食物&#xff1a; food_list []while True:c input("输入1添加新的食物&#xff0c;输入2查询已添加的食物&#xff0c;输入exit退出&#xff1a;")if c "1":new_food input("输入你…...

【SPIE出版,EI检索稳定】2024年人机交互与虚拟现实国际会议(HCIVR 2024,11月15-17日)

2024年人机交互与虚拟现实国际会议&#xff08;HCIVR 2024&#xff09; 2024 International Conference on Human-Computer Interaction and Virtual Reality 官方信息 会议官网&#xff1a;www.hcivr.org 2024 International Conference on Human-Computer Interaction and …...

做58同城的网站要多少钱/佛山网站营销推广

要背诵 import java.lang.Math.*; Math.sqrt(x) 这是对x开根号 Math.pow(x,a);这是x的a次幂 1.数值类型的转换 实线是完全继承 虚线是有丢失 int转float有精度丢失 9.40以前 2.强制类型转换 double x 9.997; int nx (int) x; //nx9 位运算算法面试 或就是有1就是1 &a…...

厦门 做网站/百度关键词优化和百度推广

其实这个APP内存优化也就是性能上的优化&#xff0c;这么说可能不太严谨哈&#xff0c;但是我认为在编码阶段应当尽量避免出现内存上的问题&#xff0c;在开发测试阶段避开这些问题的出现&#xff0c; 以免为客户带来无法挽回的损失 内存简介 RAM&#xff08;random access me…...

色情WordPress站点/web网页模板

边工作边学习&#xff0c;是目前最上乘的方法了&#xff01; 自学&#xff0c;不行&#xff0c;您的状态不允许&#xff0c;需要有生存的收入。 然后是谋发展&#xff0c;只是边工作边学习&#xff0c;这个边工作收入低是最大的问题所在&#xff01; 以您的社会经历来说&#…...

山西省政府网站集约化建设工作/seo网站搭建是什么

重新运行 遇到这种Failed to create/delete directory xxxxx 如果是create重新运行&#xff0c;如果是delete则找到这个文件手动删除...

wordpress轮播主题/网站建设详细方案

今天在yum install 或者yum update的时候都提示段错误(core dumped)&#xff0c;然后终止运行了。复制代码代码如下:[rootlee ~]# yum -y updateLoaded plugins: fastestmirror, refresh-packagekitDetermining fastest mirrors* base: mirror.esocc.com* extras: mirror.esocc…...

自己给公司做网站/百度网页游戏大厅

在日常工作中&#xff0c;批量管理服务器是个力气活&#xff0c;如果人工一台一台处理&#xff0c;效率低下。此时&#xff0c;老外写的pssh工具实现了批量管理。http://www.theether.org/pssh/ 它的原理是先建立ssh私钥认证&#xff0c;然后用pssh工具批量管理。 下面&#xf…...