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

【C++】bsearch函数的使用及二分法查找介绍

写程序的时候,肯定避免不了需要从集合中找到符合条件的元素,一般情况下,最简单也最常用的就是循环遍历元素,这种方法虽然写的简单,但是小数据量还行,但是数据过大的话,这样效率就低了。循环的时候,比如你要的数据正好在集合的最后,那就需要把前面的每一个元素都要对比一次,如果你要查找的数据,正好在前几个,那就很快找到到了。但数据这东西毕竟不是可控的。

所以,要查找,我们就要采用一点技巧和方法,在C/C++中,搜索的时候,可以使用bsearch函数来实现元素的查找,这个函数定义在头文件stdlib.h中,使用方式如下:

本文所有代码在 cygwin,gcc 11.3,gdb 11.2 中编译调试

bsearch的基本使用方法

bsearch函数的使用方法简单,函数定义如下

void* bsearch( const void *key, const void *ptr, size_t count, size_t size,int (*comp)(const void*, const void*) );

具体参数如下

key - 指向要查找的元素的指针 
ptr - 指向要检验的数组的指针 
count - 数组的元素数目 
size - 数组每个元素的字节数 
comp - 比较函数。若首个参数小于第二个,则返回负整数值,若首个参数大于第二个,则返回正整数值,若两参数等价,则返回零。 将 key 传给首个参数,数组中的元素传给第二个。 

comp函数的定义如下

int cmp(const void *a, const void *b);

cmp参数说明:a表示要查找的那个元素,b表示查找数组里的元素

举例如下,从数组f中查找x,如果找到就打印“找到11”,没找到就打印"没找到11"

#include <stdio.h>
#include <stdlib.h>  
const int x = 11;
const int f[] = { 1,3,6,9,11 };
int cmp(const void *a, const void *b) {int x1 = (int)(*(int*)a);int x2 = (int)(*(int*)b);printf("x1:%d\n", x1);printf("x2:%d\n", x2);if (x1 < x2) return -1;else if (x1 > x2) return 1;else return 0;
}
int main(int, char**) {int* c = (int*)bsearch(&x, f, 5, sizeof (int), cmp);if( c != NULL ) {printf("找到%d\n",x);}else {printf("没找到%d\n",x);}return 1;
}

输出如下

x1:11
x2:6
x1:11
x2:11
找到 11

可以看到,通过bsearch函数,从f中找到了11

但是,观察cmp函数中的两行printf代码

printf("x1:%d\n", x1);
printf("x2:%d\n", x2);

它表示打印要查找的元素,也就是上例的x,x2表示被查找的f中的某个元素,通过观察输出的结果,可以发现,虽然f数组中有{ 1,3,6,9,11 }5个元素,但实际上,比较函数并没有比较全部元素,只比较的两次就找到了11.

这就是文章开头说到的,循环遍历会降低效率,而使用bsearch会让查找速度加快,应为bsearch的查找并非遍历元素,而是采用了二分法查找,bsearch的第一个字幕b代表的就是Bisection/baɪˈsekʃən/,中文意思为“二等分"

关于二分法查找

在查找上使用二分法,是通过多次切分被查找的数组,然后和要查找的元素组做对比,具体步骤如下

假设数组为arr,要查找的元素为key,数组长度为len,进行如下操作

1.把被查找的数组长度除以2,得到的中间值mid,作为索引,去数组中取值arr[mid]

2.使用比对函数进行对比,第一步取到的arr[mid]和要查找的值key如果,返回的值小于0,也就说明要查找的值key,在数组的索引为0到mid中间。然后,修改要查找的数组起始位置,重复第一步,在0到mid中间查找

如果返回的值大于0,就说明要查找的值key,在数组的索引为mid到数组的最后一个元素之间。然后修改要查找的数组起始位置,重复第一步,在arr[mid]到最后个元素中间查找

3.重复如上2,3步,然后最终找到你要找的值

4.如果返回返回0,说明找到了,可以返回了

例如

从[1,2,3,4,5]中,找到4

  1. 5/2 = 2,先找到索引是2的3
  2. 因为3比4小,说明4在索引2以后
  3. (2+1+5)/2 = 4, 索引4就是5 ,比4大所以,在所以在索引4以前,3以后
  4. (3+4)/2 = 3,索引3就是4,找到了

以上就是使用二分法的流程

自己实现一个bsearch

void * mybsearch(const void* base, int len, int size, const void* key, int (*cmp)(const void* a, const void* b))
{size_t low = 0, high = len;while (low < high){int mid = (low + high) / 2;void * p = (void *) (((const char *) base) + (mid * size));int comret  = (*cmp) (key,p);if (comret < 0)high = mid;else if (comret > 0)low = mid + 1;elsereturn p;}return NULL;
}

然后还是刚才的代码

#include <stdio.h>
#include <stdlib.h>  
const int x = 11;
const int f[] = { 1,3,6,9,11 };
int cmp(const void *a, const void *b) {int x1 = (int)(*(int*)a);int x2 = (int)(*(int*)b);printf("x1:%d\n", x1);printf("x2:%d\n", x2);if (x1 < x2) return -1;else if (x1 > x2) return 1;else return 0;
}
int main(int, char**) {int* c = (int*)mybsearch(f,5, sizeof (int), &x, cmp);if( c != NULL ) {printf("找到%d\n",x);}else {printf("没找到%d\n",x);}return 1;
}

执行一下,看结果

x1:11
x2:6
x1:11
x2:11
找到 11

运行结果正确

知道的二分法的原理,就知道bsearch该如何使用,什么情况下,bsearch就找不到你要的元素

例如,如果把要查找的数组和要查找的元素修改为

const int x = 2;
const int f[] = { 1,3,6,9,2 };

的话,bsearch就无法从f中找到2,因为你的数组并不是单调的,按照二分法的查找方式,就找不到
在这里插入图片描述

所以,使用bsearch时候,如果不能确认数组是排序好的,就要先调用qsort把数组排序好,然后在使用查找

在这里插入图片描述
如上例,经过qsort以后,数据会排序好,然后就能正常使用bsearch了
在这里插入图片描述

相关文章:

【C++】bsearch函数的使用及二分法查找介绍

写程序的时候&#xff0c;肯定避免不了需要从集合中找到符合条件的元素&#xff0c;一般情况下&#xff0c;最简单也最常用的就是循环遍历元素&#xff0c;这种方法虽然写的简单&#xff0c;但是小数据量还行&#xff0c;但是数据过大的话&#xff0c;这样效率就低了。循环的时…...

分布式系统中的补偿机制设计问题

我们知道&#xff0c;应用系统在分布式的情况下&#xff0c;在通信时会有着一个显著的问题&#xff0c;即一个业务流程往往需要组合一组服务&#xff0c;且单单一次通信可能会经过 DNS 服务&#xff0c;网卡、交换机、路由器、负载均衡等设备&#xff0c;而这些服务于设备都不一…...

类成员的方法

初识对象 生活中或是程序中&#xff0c;我们都可以使用设计表格、生产表格、填写表格的形式组织数据进行对比&#xff0c;在程序中&#xff1a; 设计表格&#xff0c;称之为&#xff1a;设计类&#xff08;class&#xff09; 打印表格&#xff0c;称之为&#xff1a;创建对象 …...

华为OD机试真题Python实现【端口合并】真题+解题思路+代码(20222023)

端口合并 题目 有M(1<=M<=10)个端口组, 每个端口组是长度为N(1<=N<=100)的整数数组, 如果端口组间存在 2 个及以上不同端口相同, 则认为这 2 个端口组互相关联,可以合并 第一行输入端口组个数 M,再输入 M 行,每行逗号分隔,代表端口组。 输出合并后的端口组…...

自考本科计算机网络原理(04741)历年大题真题【18年10月-22年10月】

文章目录一、简答题&#xff08;历年真题&#xff09;18年10月-22年10月历年简答题出题情况分析2018年10月2019年4月2019年10月2020年8月2020年10月2021年4月2021年10月2022年4月2022年10月二、综合题&#xff08;历年真题&#xff09;2018年10月2019年4月2019年10月2020年8月2…...

计算机SCI期刊投稿,除了投稿信,还要做什么准备? - 易智编译EaseEditing

投稿信的准备 期刊的编辑往往需要一些有关作者及其论文的信息。 而作者也希望给编辑提供一些有助于其全文送审及决策的信息。 这些信息都应该包括在投稿信中。 投稿信应包括以下几方面的内容&#xff1a; 文题和所有作者的姓名;稿件适宜的栏目; 为什么此论文适合于在该刊而…...

Allegro如何刷新封装和库里的封装同步操作指导

Allegro如何刷新封装和库里的封装同步操作指导 在做PCB设计的过程中,有时会因为库里的封装有更新,所以PCB上使用到了这个封装时候需要和库里的同步,如下图 如何刷新,具体操作如下 点击Place点击Update Symbols...

基于Vue3手写选课组件(含时区切换,拖拽选择)

环境说明 基于vue3vite 无关联别的ui框架&#xff0c;组件化 初次使用vue3&#xff0c;技术菜&#xff0c;大佬勿喷 main.ts "moment": "^2.29.4","moment-timezone": "^0.5.41",import moment from moment; import momentTz from &…...

准备好了吗?加入 GDE 成长计划,成为下一位谷歌开发者专家!

谷歌开发者专家 (Google Developer Experts&#xff0c;GDE)&#xff0c;又称谷歌开发者专家项目&#xff0c;是由一群经验丰富的技术专家、具有社交影响力的开发者和思想领袖组成的全球性社区。通过在各项活动演讲以及各个平台上发布优质内容来积极助力开发者、企业和技术社区…...

搭建帮助中心的 8 个最佳工具

网站帮助中心的作用通过向客户表明您了解他们所面临的问题以及如何提供帮助来建立信任&#xff1b;通过回答常见问题来改善客户服务&#xff0c;增强专业的品牌形象&#xff1b;通过减少重复发送给支持人员的电话和电子邮件&#xff0c;节省时间和金钱&#xff1b;增强您在搜索…...

LQB小板焊接V3版本的小板原理图,PCB图,注意事项和步骤

第一部分&#xff0c;这个部分&#xff0c;可以不焊接&#xff0c;直接用买的下载器进行下载代码&#xff0c;外接一个下载器&#xff0c;网上大概是10元左右&#xff0c;以后学习stm32的芯片的时候&#xff0c;这个下载器就是一个串口转换器&#xff0c;也可以使用。。 当然也…...

华为OD机试真题Python实现【翻转单词顺序】真题+解题思路+代码(20222023)

翻转单词顺序 题目 输入一个英文文章片段 翻转指定区间的单词顺序,标点符号和普通字母一样处理 例如输入字符串 I am a developer. 区间[0,3]则输出 developer. a am I 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输入 使用换行隔…...

微机原理和计算机组成原理复习

1&#xff1a;冯诺依曼机器的主要特点&#xff1f; 1&#xff09;计算机由运算器、存储器、控制器、输入设备和输出设备五大部分组成&#xff1b; 2&#xff09;指令和数据存储在存储器中&#xff0c;并可以按地址访问&#xff1b; 3&#xff09;指令和数据均以二进制表示&…...

mysql5.7.33安装配置教程【保姆级安装教程】

MySQL5.7.33安装教程 1、官方网站下载 点击这里跳转页面下载 1.1、看下你是什么系统&#xff0c;系统是64位还是32位 2、解压到D盘跟路径或者其下面纯英文路径 2.1、可见它没有data、log等文件夹&#xff0c;不需手动添加(下面执行命令自动初始化)&#xff01;&#xff01; …...

每天都和时间序列打交道,我总结了这篇文章!

Datawhale干货 作者&#xff1a;戳戳龍&#xff0c;上海交通大学&#xff0c;量化算法工程师前言&#x1f534; 平时工作中每天都在和时间序列打交道&#xff0c;对时间序列分析进行研究是有必要的&#x1f7e1; 分享和交流一些自己的在时序处理方面的心得&#xff0c;提供一…...

【Leetcode——重排链表】

文章目录一、重排链表思路1.思路2.总结一、重排链表 对于这道题&#xff0c;有两种思路&#xff1a; 思路1. 1.使用一个线性表&#xff0c;存储链表中的每个节点&#xff0c;然后按照题目的条件&#xff0c;来链接线性表的各个节点即可。 使用左下标和右下标来定位线性表中的…...

HCIP总结(一)

抽象语言---编码---二进制---电信号----处理电信号 &#xff08;电脑工作流程&#xff09; OSI参考模型 ----OSI/RM (核心思想&#xff1a;分层) 应用层----提供各种应用服务&#xff0c;将抽象语言转换成编码&#xff0c;提供人机交互的接口 表示层----将编码转换成二进制 …...

华为OD机试真题Python实现【黑板上色】真题+解题思路+代码(20222023)

题目 疫情过后希望小学终于又重新开学了,3 年 2 班开学第一天的任务是将后面的黑板报重新制作, 黑板上已经写上了N个正整数,同学们需要给这每个数分别上一种颜色, 为了让黑板报既美观又有学习意义,老师要求同种颜色的所有数都可以被这个颜色中最小的那个数整除, 现在帮小…...

C++中的利器——模板

前文本文主要是讲解一下C中的利器——模板&#xff0c;相信铁子们在学完这一节后&#xff0c;写代码会更加的得心应手&#xff0c;更加的顺畅。一&#xff0c;泛型编程想要学习模板&#xff0c;我们要先了解为什么需要模板&#xff0c;我们可以看看下面这个程序。int add(int&a…...

k8s控制器

目录 一、控制器简介 二、控制器类型 1、RC和RS 2、Deployment 3、DaemonSet 4、Job 5、CronJob 6、StateFulSet 7、HPA 一、控制器简介 在kubernetes中&#xff0c;按照Pod的创建方式可以将其分为两类&#xff1a; 自主式:kubernetes直接创建出来的Pod&#xff0c;…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...