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

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