C++

参考

<cstdlib> (stdlib.h)

函数
<cstdlib>

bsearch

void* bsearch (const void* key, const void* base,               size_t num, size_t size,               int (*compar)(const void*,const void*));
在数组中进行二分搜索
在 base 指向的数组中搜索给定的 key（该数组由 num 个元素组成，每个元素大小为 size 字节），如果找到，则返回一个指向匹配元素的 void* 指针。

为了执行搜索，该函数会进行一系列对 compar 的调用，其中 key 作为第一个参数，base 指向的数组中的元素作为第二个参数。

因为此函数可能会被优化以使用非线性搜索算法（可能是二分搜索），所以使用 compar 比较时，小于 key 的元素应排在等于 key 的元素之前，而等于 key 的元素应排在大于 key 的元素之前。任何使用与 compar 相同标准排序的数组（如同使用 qsort 排序）都满足此要求。

参数

key
指向用作搜索键的对象的指针，类型转换为 void*。
base
指向要进行搜索的数组的第一个对象的指针，类型转换为 void*。
num
base 指向的数组中的元素数量。
size_t 是一个无符号整数类型。
size
数组中每个元素的大小（以字节为单位）。
size_t 是一个无符号整数类型。
compar
指向一个比较两个元素的函数的指针。
此函数被 bsearch 反复调用，以将 key 与 base 中的单个元素进行比较。它应遵循以下原型：
1
 
int compar (const void* pkey, const void* pelem);
该函数接受两个指针作为参数：第一个始终是 key，第二个指向数组中的一个元素（两者都类型转换为 const void*）。函数应（以稳定和可传递的方式）返回：
返回值含义
<0pkey 指向的元素位于 pelem 指向的元素之前
0pkey 指向的元素与 pelem 指向的元素等价
>0pkey 指向的元素位于 pelem 指向的元素之后

对于可以使用常规关系运算符进行比较的类型，一个通用的 compar 函数可能如下所示：

1
2
3
4
5
6
 
int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
}

返回值

一个指向数组中与搜索 key 匹配的条目的指针。如果存在多个匹配的元素（即，compar 会返回 0 的元素），则此指针可能指向其中的任何一个（不一定是第一个）。
如果未找到 key，则返回空指针。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
/* 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;
}

在此示例中，compareints 将两个参数指向的值作为 int 值进行比较，并返回它们所指值的差值。如果它们相等，则结果为 0；如果 a 指向的值大于 b 指向的值，则结果为正数；如果 b 指向的值更大，则结果为负数。

在主函数中，目标数组在调用 bsearch 搜索值之前，先用 qsort 进行了排序。

输出
40 is in the array.


对于 C 字符串，strcmp 可以直接用作 bsearch 的 compar 参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
/* bsearch example with strings */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */
#include <string.h>     /* strcmp */

char strvalues[][20] = {"some","example","strings","here"};

int main ()
{
  char * pItem;
  char key[20] = "example";

  /* sort elements in array: */
  qsort (strvalues, 4, 20, (int(*)(const void*,const void*)) strcmp);

  /* search for the key: */
  pItem = (char*) bsearch (key, strvalues, 4, 20, (int(*)(const void*,const void*)) strcmp);

  if (pItem!=NULL)
    printf ("%s is in the array.\n",pItem);
  else
    printf ("%s is not in the array.\n",key);
  return 0;
}

输出
example is in the array.


复杂度

未指定，但二分搜索的复杂度通常在 num 上是对数级的，平均情况下，调用 compar 大约 log2(num)+2 次。

数据竞争

该函数访问 key 指向的对象以及 base 指向的数组中任意数量的 num 个元素，但不会修改它们中的任何一个。

异常 (C++)

如果 comp 不抛出异常，则此函数不抛出异常（无抛出保证）。

如果 key 没有指向一个长度为 size 字节的对象，或者 base 没有指向一个至少包含 num 个正确排列的、每个大小为 size 字节的元素的数组，或者 comp 的行为与上述描述不符，则会导致未定义行为。

另见

qsort
对数组元素进行排序 (函数)