二進制搜索等效`find_if`

Question

假設存儲元素的容器（在這種情況下，一個普通數組）就像

struct Foo 
    { 
    char id[8]; 
    // other members 
    }; 

現在我想找到一個Foo的ID開始於一個特定的字符串S。由於數組是按id排序的，所以我想使用二進制搜索，所以我尋找一個使用與find_if相同的接口執行二分搜索的函數。 STL中是否有這樣的函數，是否可以通過使用algorithm中的其他元素來構造，還是我需要自己實現它。

Answer 1

我相信你正在尋找std::binary_search或std::lower_bound。

Answer 2

您在尋找std::lower_bound，std::upper_bound和std::equal_range，它們需要一個輸入範圍，一個搜索值和一個可選的比較器，並要求根據比較器對範圍進行排序。

爲了您的具體的例子，我會使用std::lexicographical_compare的比較：

#include <algorithm> 
#include <iterator> 

struct IdCmp 
{ 
    bool operator()(const Foo & lhs, const Foo & rhs) const 
    { 
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id), 
             std::begin(rhs.id), std::end(rhs.id)); 
    } 
}; 

int main() 
{ 
    Foo a[100];   // populate 
    Foo b = make_needle(); 

    auto p = std::equal_range(std::begin(a), std::end(a), b, IdCmp()); 

    /* The elements with key equal to that of b are in [p.first, p.second). */ 
} 

如果你希望能夠直接搜索字符串，你的比較必須是可調用的異質同一個Foo參數和一個字符串參數。例如：

struct IdCmp 
{ 
    bool operator()(const Foo & lhs, const Foo & rhs) const 
    { 
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id), 
             std::begin(rhs.id), std::end(rhs.id)); 
    } 

    bool operator()(const Foo & lhs, const char * id) const 
    { 
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id), 
             id, id + 8); 
    } 

    bool operator()(const char * id, const Foo & rhs) const 
    { 
    return std::lexicographical_compare(id, id + 8, 
             std::begin(rhs.id), std::end(rhs.id)); 
    } 
}; 

現在您可以搜索：

std::lower_bound(std::begin(a), std::end(a), "ABCD1234", IdCmp())