bsearch-c和c++标准函数

C&C++标准库

bsearch

函数 <cstdlib>

void* bsearch (const void* key, const void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

二分查找数组

查找base(由num个元素组成，每个大小为 size)指向的数组中的给定 key，如果找到，返回指向匹配元素的void*指针。

为了执行查找，该函数执行一系列调用，将key作为第一个参数，将base指向的数组元素作为第二个参数进行比较。

因为这个函数可以优化为使用非线性搜索算法(假定是二分查找)，所以使用compare比较小于key的元素应该在比较相等的元素之前，而这些元素应该在比较较大的元素之前。这个要求可以通过与compare使用的相同标准排序的任何数组来满足(就像使用qsort排序一样)。

☲ 参数

key
指向要查找的元素的对象的指针，类型转换为void*。

base
指向执行查找的数组的第一个对象的指针，类型转换为void*。

num
数组中元素的个数.
size_t是一个无符号整型。

size
数组中每个元素的字节大小。
size_t是一个无符号整型。

compar
指向比较两个元素的函数的指针。
该函数由bsearch反复调用，以将key与base中的单个元素进行比较。它将遵循以下原型:

int compar (const void* pkey, const void* pelem);

接受两个指针作为参数:第一个指针总是key，第二个指针指向数组的一个元素(都被类型转换为const void*)。该函数将返回(以稳定和可传递的方式):

返回值	意思是
<0	pkey指向的元素在pelem指向的元素之前
0	pkey所指向的元素与pelem所指向的元素等价
>0	pkey指向的元素在pelem指向的元素之后

对于可以使用常规关系操作符进行比较的类型，一般的比较函数可能如下所示:

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

☉ 返回值

指向数组中与搜索键匹配的项的指针。如果有多个匹配的元素(例如，compare将返回0的元素)，这个可以指向其中的任何一个(不一定是第一个)。

如果没有找到key，则返回一个空指针。

☣ 示例

/* 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指向的值大于，则结果为负。

在main函数中，目标数组在调用bsearch搜索值之前使用qsort排序。

输出:
40 is in the array.

对于C字符串，strcmp可以直接用作bsearch的比较参数:

/* 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不抛出异常，则此函数不抛出异常(no-throw保证)。

如果key不指向一个size 字节长的对象，或者base不指向一个至少有num正确排列的每个size 字节的元素的数组，或者如果comp不像上面描述的那样行为，它将导致未定义的行为。

🍄 另请参阅

qsort

数组元素排序(function )