C 标准库中有二进制搜索方法吗?
Is there a Binary Search method in the C standard library?
我找不到任何实现二分查找的方法。是我没有找到,还是根本不存在?
我认为是第二个,但我找不到重复的问题,所以我可能错了。
同<stdlib.h>
中有bsearch()
方法,如所列here, here and here。
bsearch()
函数使用二进制搜索算法在大小为size的n个元素的排序数组中查找与key匹配的元素。 (类型 size_t 在 <stdlib.h>
中定义为无符号整型。)最后一个参数 compare
为 bsearch()
提供了一个指向函数的指针,它调用该函数来比较搜索键与任何数组元素。此函数必须 return 一个值,该值指示其第一个参数(搜索键)是否小于、等于或大于其第二个参数(要测试的数组元素)..
你通常应该在bsearch()
之前使用qsort()
,因为数组应该是sorted(应该是按升序排列,在搜索之前使用 compare
) 使用的相同标准排序。这一步是必要的,因为二分搜索算法会测试搜索关键字是否高于或低于数组中的中间元素,然后消除数组的一半,测试结果的中间,再次消除一半,等等。如果您为 bsearch()
定义了两个参数类型相同的比较函数,那么 qsort()
可以使用相同的比较函数。
bsearch()
函数 return 是指向找到的与搜索关键字匹配的数组元素的指针。如果没有找到匹配的元素,bsearch()
return 是一个空指针。[a]
使用示例:
/* bsearch example */
#include <stdio.h> /* printf */
#include <stdlib.h> /* qsort, bsearch, NULL */
int compareints (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int values[] = { 50, 20, 60, 40, 10, 30 };
int main ()
{
int * pItem;
int key = 40;
qsort (values, 6, sizeof (int), compareints);
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);
return 0;
}
输出:
40 is in the array.
回应下面关于如何找到第一个元素 less/greater 而不是 key
的评论,这里是 (可能是脏的) 解决方法:您可以遍历排序数组并使用传递给此方法的相同 compare
函数将其元素与 key
进行比较,直到找到元素 less/greater 比 key
.
C 库有一个标准函数 bsearch
,在 <stdlib.h>
中声明,正是为了这个目的:在 table 条目中找到一个匹配的条目,根据给定的比较函数。
这是 C 标准中的规范:
7.22.5.1 The
bsearch
functionSynopsis
#include <stdlib.h> void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
Description
The
bsearch
function searches an array ofnmemb
objects, the initial element of which is pointed to bybase
, for an element that matches the object pointed to bykey
. The size of each element of the array is specified bysize
.The comparison function pointed to by
compar
is called with two arguments that point to the key object and to an array element, in that order. The function shall return an integer less than, equal to, or greater than zero if the key object is considered, respectively, to be less than, to match, or to be greater than the array element. The array shall consist of: all the elements that compare less than, all the elements that compare equal to, and all the elements that compare greater than the key object, in that order.308)Returns
The
bsearch
function returns a pointer to a matching element of the array, or a null pointer if no match is found. If two elements compare as equal, which element is matched is unspecified.
308) In practice, the entire array is sorted according to the comparison function.
这个函数有两个缺点:
- 如果 table 包含重复的匹配条目,未指定将 returned 哪个条目,如上文最后一段所强调的。
- 如果在 table 中找不到该函数,则无法使用该函数定位插入条目的位置,它只是 return 一个空指针。
这是一个简单的实现,它修复了第一点(它被编码为总是 return 最接近数组开头的匹配条目)并且可以修改以解决第二点:
#include <stdlib.h>
void *bsearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
const unsigned char *p;
size_t m;
int r;
while (nmemb > 0) {
m = (nmemb - 1) >> 1;
p = (const unsigned char *)base + m * size;
if ((r = compar(key, p)) < 0) {
nmemb = m;
} else
if (r > 0) {
base = p + size;
nmemb -= m + 1;
} else
if (m == 0) {
return (void *)p;
} else {
/* continue search to return first matching entry */
nmemb = m + 1;
}
}
// if you want the insertion point, you can return p here
return NULL;
}