C語言中可以用bsearch()實現二分查找。同qsort()一樣，bsearch()也包含在glibc庫中，且同樣要自定義比較函數。其原型如下：
void *bsearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
key指向所要查找的元素，base指向進行查找的數組，nmemb為查找長度，一般為數組長度，size為每個元素所占的字節數，一般用sizeof(...)表示，compar指向比較函數，它定義比較的規則。需要注意的是，數據必須是經過預先排序的，而排序的規則要和compar所指向比較函數的規則相同。如果查找成功則返回數組中匹配元素的地址，反之則返回空。對於有多於一個的元素匹配成功的情況，bsearch()未定義返回哪一個。
bsearch實現（glibc）
從glibc的代碼可以看到，bsearch的實現是很簡潔的：
/* Perform a binary search for KEY in BASE which has NMEMB elements
of SIZE bytes each. The comparisons are done by (*COMPAR)(). */
void *
bsearch (const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
size_t l, u, idx;
const void *p;
int comparison;
l = 0;
u = nmemb;
while (l < u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = (*compar) (key, p);
if (comparison < 0)
u = idx;
else if (comparison > 0)
l = idx + 1;
else
return (void *) p;
}
return NULL;
}
bsearch_less的實現
參考bsearch的實現，我們可以實現bsearch的變形，來找到不大於key的最接近的那個數：
void *
bsearch_less (const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
int l, u, idx;
const void *p;
int comparison;
l = 0;
u = nmemb - 1;
while (l <= u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = (*compar) (key, p);
if (comparison < 0)
u = idx - 1;
else if (comparison > 0)
l = idx + 1;
else
return (idx == 0) ? NULL : (void *) (((const char *) p) - size);
}
return (u < 0) ? NULL : (void *) (((const char *) base) + (u * size));
}
bsearch_more的實現
參考bsearch的實現，我們可以實現bsearch的變形，來找到不小於key的最接近的那個數：
void *
bsearch_more(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
int l, u, idx;
const void *p;
int comparison;
l = 0;
u = nmemb - 1;
while (l <= u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = (*compar) (key, p);
if (comparison < 0)
u = idx - 1;
else if (comparison > 0)
l = idx + 1;
else
return (idx == u) ? NULL : (void *) (((const char *) p) + size);
}
return (l > nmemb - 1) ? NULL : (void *) (((const char *) base) + (l * size));
}
示例：
/* bsearch example */
#include <stdio.h> /* printf */
#include <stdlib.h> /* qsort, bsearch, NULL */
void *
bsearch_less (const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
int l, u, idx;
const void *p;
int comparison;
l = 0;
u = nmemb - 1;
while (l <= u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = (*compar) (key, p);
if (comparison < 0)
u = idx - 1;
else if (comparison > 0)
l = idx + 1;
else
return (idx == 0) ? NULL : (void *) (((const char *) p) - size);
}
return (u < 0) ? NULL : (void *) (((const char *) base) + (u * size));
}
void *
bsearch_more(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
int l, u, idx;
const void *p;
int comparison;
l = 0;
u = nmemb - 1;
while (l <= u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = (*compar) (key, p);
if (comparison < 0)
u = idx - 1;
else if (comparison > 0)
l = idx + 1;
else
return (idx == u) ? NULL : (void *) (((const char *) p) + size);
}
return (l > nmemb - 1) ? NULL : (void *) (((const char *) base) + (l * size));
}
int compareints (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
//int values[] = { 50, 20, 60, 40, 10, 30 };
int values[] = { 50, 20, 60, 30, 10, 30 };
void test_bsearch_less(int key)
{
int* pItem = (int*) bsearch_less (&key, values, 6, sizeof (int), compareints);
if (pItem!=NULL)
printf ("%d is nearest less than %d int the array.\n",*pItem, key);
else
printf ("no key is less than %d in the array.\n",key);
}
void test_bsearch(int key)
{
int* pItem = (int*) bsearch (&key, values, 6, sizeof (int), compareints);
if (pItem!=NULL)
printf ("%d is in the array.\n",*pItem);
else
printf ("%d is not in the array.\n",key);
}
void test_bsearch_more(int key)
{
int* pItem = (int*) bsearch_more(&key, values, 6, sizeof (int), compareints);
if (pItem!=NULL)
printf ("%d is nearest more than %d int the array.\n",*pItem, key);
else
printf ("no key is more than %d in the array.\n",key);
}
void print_values(int* base, size_t nmemb)
{
printf("values: ");
for (size_t i = 0; i < nmemb; ++i)
{
printf("%d ", *(base+i));
}
printf("\n");
}
int main(int argc, char** argv)
{
if (argc < 2)
{
printf("usage: ./bsearch_example num\n");
return -1;
}
int key = atoi(argv[1]);
qsort (values, 6, sizeof (int), compareints);
print_values(values,6);
test_bsearch(key);
test_bsearch_less(key);
test_bsearch_more(key);
return 0;
}
運行結果：
[root@VM_174_171_CentOS algorithm]# ./bsearch_example 1
values: 10 20 30 30 50 60
1 is not in the array.
no key is less than 1 in the array.
10 is nearest more than 1 int the array.
[root@VM_174_171_centos algorithm]# ./bsearch_example 10
values: 10 20 30 30 50 60
10 is in the array.
no key is less than 10 in the array.
20 is nearest more than 10 int the array.
[root@VM_174_171_centos algorithm]# ./bsearch_example 30
values: 10 20 30 30 50 60
30 is in the array.
20 is nearest less than 30 int the array.
30 is nearest more than 30 int the array.
[root@VM_174_171_centos algorithm]# ./bsearch_example 55
values: 10 20 30 30 50 60
55 is not in the array.
50 is nearest less than 55 int the array.
60 is nearest more than 55 int the array.
[root@VM_174_171_centos algorithm]# ./bsearch_example 60
values: 10 20 30 30 50 60
60 is in the array.
50 is nearest less than 60 int the array.
no key is more than 60 in the array.
[root@VM_174_171_centos algorithm]# ./bsearch_example 61
values: 10 20 30 30 50 60
61 is not in the array.
60 is nearest less than 61 int the array.
no key is more than 61 in the array.
