Где я могу получить “полезный” алгоритм двоичного поиска C++?
5 ответов
Нет таких функций, но можно записать простой с помощью std::lower_bound , std::upper_bound или std::equal_range .
А простая реализация могла быть
template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
// Finds the lower bound in at most log(last - first) + 1 comparisons
Iter i = std::lower_bound(begin, end, val);
if (i != end && !(val < *i))
return i; // found
else
return end; // not found
}
, Другое решение будет состоять в том, чтобы использовать std::set, который гарантирует упорядочивание элементов и предоставляет метод iterator find(T key), который возвращает итератор данному объекту. Однако Ваши требования не могли бы быть совместимы с использованием набора (например, если необходимо сохранить тот же элемент многократно).
Необходимо взглянуть на std::equal_range. Это возвратит пару итераторов к диапазону всех результатов.
Существует ряд их:
http://www.sgi.com/tech/stl/table_of_contents.html
Поиск:
На отдельной ноте:
Они, вероятно, думали, что поиск контейнеров мог назвать больше чем один результат. Но в нечетном случае, где просто необходимо протестировать на существование, оптимизированная версия также была бы хороша.
Проверьте эту функцию, qBinaryFind:
RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )Работает, двоичный поиск диапазона [начинаются, конец), и возвращает положение возникновения значения. Если нет никаких случаев значения, конца возвратов.
объекты в диапазоне [начинаются, конец) должен быть отсортирован в порядке возрастания; см. qSort ().
, Если существует много случаев того же значения, любой из них мог бы быть возвращен. Используйте qLowerBound () или qUpperBound () при необходимости в более прекрасном управлении.
Пример:
QVector<int> vect; vect << 3 << 3 << 6 << 6 << 6 << 8; QVector<int>::iterator i = qBinaryFind(vect.begin(), vect.end(), 6); // i == vect.begin() + 2 (or 3 or 4)
функция включена в <QtAlgorithms> заголовок, который является частью библиотека Qt .