Добавить бинарный поиск возвращающий итератор

[Roman-Koshelev]

Думаю этот велосипед писал каждый.

Реализация:

template<class ForwardIt, class T, class Compare>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    auto it = std::lower_bound(first, last, value, comp);
    if (it != last && comp(value, *it))
        return last;
    return it;
}

Имя нового алгоритма остается открытым

[Russkov]

я полагаю binary_search не возвращает итератор потому, что в диапазоне может быть несколько эквивалентных объектов, и в общем случае тратить несколько дополнительных итераций на поиск конкретно первого из них совершенно не обязательно.

Можно было бы назвать этот алгоритм binary_search_first, т.к. он вернет итератор первый элемент из эквивалентных.

[Roman-Koshelev]

std::lower_bound возвращает итератор на первый элемент >= преданному. Следовательно доп итераций не будет. А вот замечание что одинаковых элементов может быть несколько ценно

[tomilov]

Для поиска нескольких эквивалентных есть auto [lo, hi] = equal_range(beg, end, x); (O(logb(distance(beg,end)))). Условие lo != hi - это как раз bool, нужный @Roman-Koshelev.

[apolukhin]

Закрываю, уже есть std::equal_range

[Roman-Koshelev]

@apolukhin К сожалению этот алгоритм менее оптимален для случая когда найденный диапазон состоит из 0 или 1 элемента (а это 100% случаев которые были в моей практике). Но да с этим можно жить (однако велосипедить свой search через lower_bound все же придется)