深入理解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也同样可以。

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