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));
}