天天看点

深入理解CPP与C中bsearch函数的用法

·使用besearch函数的前提(一些废话)

首先让我们先亮出二分法的定义:

https://baike.baidu.com/item/二分法/1364267

以及二分法实现的方法:

https://blog.csdn.net/sufeiboy/article/details/54401257

这些应该是使用二分查找前需要了解的知识,综上我们可以得出:使用besearch前应该先将目标数组进行一定规律的排序,事实上大部分时候我们会使用库中自带的qsort函数进行排序。

·besearch函数的函数原型解析

(资料源于网络)

void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*cmp)(const void *, const void *));
           

解释一下参数

key: 为要查找的元素的地址

base: 指向进行查找的数组的开始地址

num: 为想要查找的范围,即在多少个数中进行二分查找

size:数组中每个元素的大小,一般用sizeof()表示

cmp:比较两个元素的函数,定义比较规则。这里我们可以类比qsort,首先对于这样一个cmp:

int cmp(const void *p1,const void *p2);

其中p1始终指向的是key的地址,而p2指向的是besearch所查找的数组里的传递过来的元素

其次我们知道qsort对于cmp函数的比较返回值的处理是当返回值为正则交换两个元素,而对于bsearch则为当返回值为0则认为查找到了目标元素。当返回值为正数则besearch会向后进行二分查找,返回值为负数将会向前进行二分查找。 简单的记忆方法便是:升序数组返回p1-p2,降序数组返回p2-p1(这里建议看完使用实例后再看)

关于besearch的返回值: besearch在找到元素后将返回数组中满足cmp条件的这个数的地址,但是这个地址是void *类型的,如果我们不加以类型转换就无法使用。而如果没有找到对应元素则会返回NULL指针,我们可以通过判断返回值的类型得到元素是否在数组中存在。

关于besearch的陷阱: 当数组中存在多个匹配元素时,besearch不能保证返回的指针一定指向某一个特定的元素,此时besearch只能用于证明数组内是否含有特定元素

·bserach的使用实例

知道了这些最基本的函数组成后,我们照猫画虎就可以写出第一个简单的二分查找了。

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p1,const void *p2)
{
    int a=*(int *)p1,b=*(int *)p2;//为了清楚说明进行临时转化保存
    return a-b;//仅当a=b时返回0,说明查找到了
}
int main(int argc, char const *argv[])
{
    int arry[100];
    for(int i=1;i<=100;i++) arry[i-1]=i;
    int *ans;//用于接受查找的结果
    int key;
    scanf("%d",&key);
    ans=(int *)bsearch(&key,arry,100,sizeof(int),cmp);//记得对结果进行转换
    if (ans!=NULL)
        printf("The key:%d exists.The pointer is %X.",key,ans);
    else 
        printf("The key doesn't exists\n");
    return 0;
}
           

四次运行实例:

输入:
13
输出:
The key:13 exists.The pointer is 61FD74.
输入:
60
输出:
The key:60 exists.The pointer is 61FD9C.
输入:
0
输出:
The key doesn't exists
输入:
101
输出
The key doesn't exists
           

·更加灵活的使用beserch

我们知道,上述的数组是一个升序数组,那么考虑一下情况,如果arry是一个 100 99 98…… 2 1的降序数组此时我们该如何编写cmp函数

其实很简单,根据cmp返回值对besearch的影响,我只需把return语句重写

原本:
int cmp(const void *p1,const void *p2)
{
    int a=*(int *)p1,b=*(int *)p2;
    return a-b;
}
现在
int cmp(const void *p1,const void *p2)
{
    int a=*(int *)p1,b=*(int *)p2;
    return b-a;
}
           

是不是很像qsort的处理方式呢

更进一步的,如果我们要寻找这样一个元素它恰好是key的三倍,那么我们可以这么写:

int cmp(const void *p1,const void *p2)
{
    int a=*(int *)p1,b=*(int *)p2;
    return 3*a-b;//这里默认arry进行升序排列
}
           

至此,关于besearch的基本部分便已陈述完毕,实际上我们可以通过besearch进行更复杂的查找,正如网上很多的关于qsort对结构体进行一级甚至多级排序,besearch也同样可以。

本文在此结束,但读者可以自行去探索。

继续阅读