std::bsearch
來自 cppreference.com
| 定義於標頭檔案 <cstdlib> |
||
| void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* c-compare-pred */* comp ); |
(1) | |
| extern "C" using /* c-compare-pred */ = int(const void*, const void*); extern "C++" using /* compare-pred */ = int(const void*, const void*); |
(2) | (僅作說明*) |
在由 ptr 指向的陣列中查詢等於由 key 指向的元素。該陣列包含 count 個元素，每個元素大小為 size 位元組，並且必須相對於由 key 指向的物件進行分割槽，也就是說，所有比較小於鍵的元素必須出現在所有比較等於鍵的元素之前，而所有比較等於鍵的元素必須出現在所有比較大於鍵的元素之前。一個完全排序的陣列滿足這些要求。元素使用由 comp 指向的函式進行比較。
如果陣列尚未按照 comp 使用的相同準則，按鍵的升序分割槽，則行為未定義。
如果陣列包含多個 comp 會指示與所搜尋元素相等的元素，則函式返回哪個元素作為結果是未指定的。
目錄 |
[編輯] 引數
| key | - | 指向要搜尋的元素的指標 |
| ptr | - | 指向要檢查的陣列的指標 |
| count | - | 陣列中元素的數量 |
| size | - | 陣列中每個元素的位元組大小 |
| comp | - | 比較函式，如果第一個引數“小於”第二個引數，則返回負整數值；如果第一個引數“大於”第二個引數，則返回正整數值；如果引數相等，則返回零。key 作為第一個引數傳入，陣列中的一個元素作為第二個引數傳入。 比較函式的簽名應等效於以下內容 int cmp(const void *a, const void *b); 該函式不得修改傳遞給它的物件，並且在對相同物件進行呼叫時必須返回一致的結果，無論它們在陣列中的位置如何。 |
[編輯] 返回值
指向找到的元素的指標，如果未找到元素則為空指標。
[編輯] 注意
儘管有這個名字，但 C 和 POSIX 標準都不要求此函式使用二分查詢實現，也不提供任何複雜性保證。
C++ 標準庫提供的兩個過載是不同的，因為引數 comp 的型別不同（語言連結是其型別的一部分）。
[編輯] 示例
執行此程式碼
#include <array> #include <cstdlib> #include <iostream> template<typename T> int compare(const void *a, const void *b) { const auto &arg1 = *(static_cast<const T*>(a)); const auto &arg2 = *(static_cast<const T*>(b)); const auto cmp = arg1 <=> arg2; return cmp < 0 ? -1 : cmp > 0 ? +1 : 0; } int main() { std::array arr{1, 2, 3, 4, 5, 6, 7, 8}; for (const int key : {4, 8, 9}) { const int* p = static_cast<int*>( std::bsearch(&key, arr.data(), arr.size(), sizeof(decltype(arr)::value_type), compare<int>)); std::cout << "value " << key; if (p) std::cout << " found at position " << (p - arr.data()) << '\n'; else std::cout << " not found\n"; } }
輸出
value 4 found at position 3 value 8 found at position 7 value 9 not found
[編輯] 參閱
| 對未指定型別的元素範圍進行排序 (函式) | |
| 返回與特定鍵匹配的元素範圍 (函式模板) | |
| C 文件 對應於 bsearch
| |
