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
對陣列元素進行排序 (函式)