std::binary_search与lower_bound/upper_bound配合使用
详述std::binary_search、std::lower_bound和std::upper_bound的区别和配合方式。binary_search的返回值是什么？如何利用lower_bound/upper_bound在有序范围中查找元素范围？
回答
我还是少年
std::binary_search(first,last,val)返回bool——仅判断val是否存在(要求已排序)。底层通常调用lower_bound再比较。std::lower_bound返回首个≥val的迭代器；std::upper_bound返回首个**>val**的迭代器。两者组合可获得val的范围：[lower, upper)。时间复杂度均为O(log n)（要求随机访问迭代器；forward_iterator退化为O(n)）。三者都要求范围已按同一比较函数排序。注意：std::binary_search的true返回不保证元素位置；要获取位置用lower_bound。C++20引入std::ranges::binary_search等简化调用。对于multiset/multimap可用equal_range一次返回pair。