bsearch, bsearch_s

 

C

編譯器支援

語言

標頭檔案

型別支援

程式工具

變參函式支援

錯誤處理

動態記憶體管理

字串庫

演算法

數值

日期和時間工具

輸入/輸出支援

本地化支援

併發支援 (C11)

技術規範

符號索引

 

演算法

qsortqsort_s (C11 起)

bsearchbsearch_s (C11 起)

 

在標頭檔案 <stdlib.h> 中定義
void* bsearch( const void *key, const void *ptr, size_t count, size_t size,                int (*comp)(const void*, const void*) );	(1)
void* bsearch_s( const void *key, const void *ptr, rsize_t count, rsize_t size,                  int (*comp)(const void *, const void *, void *),                  void *context );	(2)	(C11 起)
/*QVoid*/* bsearch( const void *key, /*QVoid*/ *ptr, size_t count, size_t size,                     int (*comp)(const void*, const void*) );	(3)	(自 C23 起)
/*QVoid*/* bsearch_s( const void *key, /*QVoid*/ *ptr, rsize_t count, rsize_t size,                       int (*comp)(const void *, const void *, void *),                       void *context );	(4)	(自 C23 起)

1) 在 ptr 指向的陣列中查詢等於 key 所指向元素的元素。該陣列包含 count 個大小為 size 位元組的元素，並且必須相對於 key 進行分割槽，即所有比較結果小於 key 的元素必須出現在所有比較結果等於 key 的元素之前，而這些元素又必須出現在所有比較結果大於 key 的元素之前。一個完全排序的陣列滿足這些要求。元素使用 comp 指向的函式進行比較。如果陣列尚未根據 comp 使用的相同準則以升序對 *key 進行分割槽，則行為未定義。

2) 同 (1)，但額外狀態引數 context 會傳遞給 comp，並且在執行時會檢測以下錯誤並呼叫當前安裝的約束處理函式

• count 或 size 大於 RSIZE_MAX
• key、ptr 或 comp 是空指標（除非 count 為零）

如同所有邊界檢查函式，僅當實現定義了 __STDC_LIB_EXT1__ 且使用者在包含 <stdlib.h> 之前將 __STDC_WANT_LIB_EXT1__ 定義為整數常量 1 時，才保證 bsearch_s （以及對應的泛型宏）(C23 起) 可用。

3,4) 分別等價於 (1) 和 (2) 的泛型宏。令 T 為非限定物件型別（包括 void）。

• 若 ptr 的型別為 const T*，則返回型別為 const void*。
• 否則，若 ptr 的型別為 T*，則返回型別為 void*。
• 否則，行為未定義。

如果這些泛型函式的宏定義被抑制以訪問實際函式（例如，如果使用了 (bsearch)、(bsearch_s) 或函式指標），則實際函式宣告 (1) 或 (2) 變為可見。

如果陣列中包含多個 comp 指示為等於所搜尋元素的元素，則函式返回哪個元素作為結果是未指定的。

實際函式 (1) 和 (2) 的直接使用已棄用。

(自 C23 起)

引數

key	-	指向要搜尋的元素的指標
ptr	-	指向要檢查的陣列的指標
count	-	陣列中的元素數量
size	-	陣列中每個元素的位元組大小
comp	-	比較函式，如果第一個引數小於第二個引數，則返回負整數值；如果第一個引數大於第二個引數，則返回正整數值；如果引數相等，則返回零。key 作為第一個引數傳入，陣列中的元素作為第二個引數傳入。 比較函式的簽名應等效於以下內容  int cmp(const void *a, const void *b); 該函式不得修改傳遞給它的物件，並且在對相同物件進行呼叫時必須返回一致的結果，無論它們在陣列中的位置如何。 ​
context	-	比較器的狀態（例如，排序序列），作為第三個引數傳遞給 comp

返回值

1) 指向陣列中與 *key 相等的元素的指標，如果未找到此類元素則返回空指標。

2) 同 (1)，但執行時約束違規時也返回空指標。

3,4) 分別同 (1) 和 (2)，但 cv-限定符已調整。

注意

儘管有其名稱，但 C 或 POSIX 標準都不要求此函式使用二分搜尋實現，也不做任何複雜性保證。

與其他邊界檢查函式不同，bsearch_s 不將大小為零的陣列視為執行時約束違規，而是指示未找到元素（唯一接受大小為零的陣列的其他函式是 qsort_s）。

在 bsearch_s 之前，bsearch 的使用者通常使用全域性變數來表示比較器的狀態。

示例

執行此程式碼

#include <stdlib.h>
#include <stdio.h>
 
struct data {
    int nr;
    char const *value;
} dat[] = {
    {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"}
};
 
int data_cmp(void const *lhs, void const *rhs) 
{
    struct data const *const l = lhs;
    struct data const *const r = rhs;
 
    if (l->nr < r->nr) return -1;
    else if (l->nr > r->nr) return 1;
    else return 0;
 
    // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut
    // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present)
}
 
int main(void) 
{
    struct data key = { .nr = 3 };
    struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0],
                                     sizeof dat[0], data_cmp);
    if (res) {
        printf("No %d: %s\n", res->nr, res->value);
    } else {
        printf("No %d not found\n", key.nr);
    }
}

輸出

No 3: Hello

參考

• C17 標準 (ISO/IEC 9899:2018)

• 7.22.5.1 The bsearch function (p: 258)

• K.3.6.3.1 The bsearch_s function (p: 441-442)

• C11 標準 (ISO/IEC 9899:2011)

• 7.22.5.1 The bsearch function (p: 355)

• K.3.6.3.1 The bsearch_s function (p: 608-609)

• C99 標準 (ISO/IEC 9899:1999)

• 7.20.5.1 The bsearch function (p: 318-319)

• C89/C90 標準 (ISO/IEC 9899:1990)

• 4.10.5.1 The bsearch function

參閱

qsortqsort_s (C11 起)	對未指定型別的元素範圍進行排序 (function)
C++ documentation for bsearch