二进制搜索等效`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())