std::binary_search возвращающий итератор

Иногда требуется делать поиск в отсортированном std::vector, однако в STL есть лишь std::binary_search которая возвращает bool. Нижеприведенная binary_find возвращает итератор на первый найденный элемент, или же итератор last если такого элемента в векторе не существует.

// Function like binary_search, but returns iterator, not bool
template <class ForwardIterator, class T>
ForwardIterator binary_find(ForwardIterator first,
ForwardIterator last, const T& value)
{
    first = std::lower_bound(first, last, value);
    if (first!=last && !(value < *first))
        return first; //found
    return last;
};
Advertisements

2 thoughts on “std::binary_search возвращающий итератор

  1. Ещё вариант: std::equal_range возвращает пару итераторов. если они равны, то элемент не найден, если не равны, то первый итератор указывает на искомый объект. плюс в том, что equal_range уже написан (не надо изобретать велосипед) и в том, что перегружен для работы с функторами.

  2. Минус std::equal_range в том, что он делает больше сравнений – двоичный поиск нижней границы, двоичный поиск верхней границы. В худшем случае 2*log(n). binary_find делает один двоичный поиск.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s