在C++中,二分查找函数通常使用std::binary_search
或std::lower_bound
进行实现。这两个函数都需要一个比较器函数作为参数来确定元素的顺序。
比较器函数通常是一个lambda函数或者一个自定义的结构体,用来比较两个元素的大小。比较器函数需要满足以下条件:
a
小于b
,则返回true
a
等于b
,则返回false
a
大于b
,则返回false
比较器函数的定义示例如下:
// lambda函数
auto cmp = [](int a, int b) { return a < b; };
// 结构体
struct Compare {
bool operator()(int a, int b) const {
return a < b;
}
};
// 使用lambda函数作为比较器
std::binary_search(arr.begin(), arr.end(), target, cmp);
// 使用结构体作为比较器
std::lower_bound(arr.begin(), arr.end(), target, Compare());
根据比较器函数的定义,可以根据具体的需求来选择不同的比较器。比如,如果需要按照降序排列,则可以将比较器函数修改为return a > b;
。