二分查找及其变形

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. ",*pItem, key）;
else
printf （"no key is less than %d in the array. ",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. ",*pItem）;
else
printf （"%d is not in the array. ",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. ",*pItem, key）;
else
printf （"no key is more than %d in the array. ",key）;
}void print_values（int* base, size_t nmemb）
{
printf（"values: "）;
for （size_t i = 0; i < nmemb; ++i）
{
printf（"%d ", *（base+i））;
}
printf（" "）;
}int main（int argc, char** argv）
{
if （argc < 2）
{
printf（"usage: ./bsearch_example num "）;
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 1values: 10 20 30 30 50 601 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 10values: 10 20 30 30 50 6010 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 30values: 10 20 30 30 50 6030 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 55values: 10 20 30 30 50 6055 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 60values: 10 20 30 30 50 6060 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 61values: 10 20 30 30 50 6061 is not in the array.60 is nearest less than 61 int the array.no key is more than 61 in the array.本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-01/127433.htm