Где взять "полезный" алгоритм двоичного поиска C++?
Мне нужен алгоритм двоичного поиска, совместимый с контейнерами C++ STL, что-то вроде std::binary_search в заголовке стандартной библиотеки <algorithm>, но мне нужно, чтобы он возвращал итератор, указывающий на результат, а не простое логическое значение, сообщающее мне, существует ли элемент.
(Кстати, о чем, черт возьми, думал стандартный комитет, когда они определили API для binary_search ?!)
Меня больше всего беспокоит то, что мне нужна скорость двоичного поиска, поэтому, хотя я могу найти данные с помощью других алгоритмов, как указано ниже, я хочу воспользоваться тем фактом, что мои данные сортируются, чтобы получить преимущества двоичного поиск, а не линейный поиск.
пока что lower_bound и upper_bound не работают, если данные отсутствуют:
//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6
Примечание: Я также могу использовать алгоритм, который не принадлежит пространству имен std, если он совместим с контейнерами. Например, boost::binary_search.
Вы должны проверить равенство после использования (нижний / верхний) _bound (см. Ответ ниже).
В документации lower_bound и upper_bound указано, что диапазон должен быть отсортирован, и поэтому они могут быть реализованы как двоичный поиск.
@vividos, ура! вы нашли только ту часть документации, о которой мне нужно было знать! Спасибо!
Роберт, алгоритмы lower / upper_bound / equal_range не работают с несортированными диапазонами. Вам просто повезло увидеть, как они работают с выбранным вами образцом элементов.
@ Люк Эрмитт, да, вы совершенно правы, еще раз спасибо!
мой первый взгляд обычно идет на sgi.com/tech/stl. Он документирует STL до того, как C++ включил его в стандартную библиотеку C++, но большая часть документации остается действительной.
Меня также часто сбивает с толку std::lower_bound, но я считаю, что это способ бинарного поиска, см. здесь. Вам просто нужно проверить конец, а затем равенство с вашей иглой, вместо того, чтобы просто проверять конец. Это лишь небольшая постоянная стоимость, и lower_bound должен быть таким же быстрым, как binary_search, если ваши данные не содержат много повторений, и в этом случае binary_search может найти иглу немного быстрее, если она присутствует (если это не так, тогда ему нужно найти в любом случае нижняя / верхняя граница).
Я: STL, поищите это значение в моем отсортированном контейнере. СТЛ: Да, это там. Я: вздох, а где это? STL: Я могу сказать вам, где есть значение, равное или большее. Я: вздох, так что я должен проверить себя, действительно ли это найденный результат или что-то большее?
Ответы 9
Вам стоит взглянуть на std::equal_range. Он вернет пару итераторов к диапазону всех результатов.
Согласно cplusplus.com/reference/algorithm/equal_range стоимость std :: equal_range примерно вдвое выше, чем std :: lower_bound. Похоже, что он завершает вызов std :: lower_bound и вызов std :: upper_bound. Если вы знаете, что ваши данные не имеют дубликатов, то это излишне, и std :: lower_bound (как показано в верхнем ответе) - лучший выбор.
@BruceDawson: cplusplus.com предоставляет только реализацию Справка для указания поведение; для реальной реализации вы можете проверить свою любимую стандартную библиотеку. Например, в llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm мы видим, что вызовы lower_bound и upper_bound выполняются на непересекающихся интервалах (после некоторого ручного двоичного поиска). При этом, вероятно, это будет дороже, особенно для диапазонов с несколькими совпадающими значениями.
Их множество:
http://www.sgi.com/tech/stl/table_of_contents.html
Искать:
Отдельно отметим:
Вероятно, они думали, что поиск контейнеров может дать более одного результата. Но в странном случае, когда вам просто нужно проверить наличие, оптимизированная версия также будет хороша.
binary_search не возвращает итератор, как я упоминал ранее, поэтому я ищу альтернативу.
Да, я знаю. Но он вписывается в набор алгоритмов бинарного поиска. Так что другим приятно знать об этом.
binary_search, как и многие другие вещи в STL, назван неправильно. Я ненавижу это. Проверка существования - это не то же самое, что поиск чего-либо.
Эти функции двоичного поиска бесполезны, если вы хотите узнать индекс искомого элемента. Для этой задачи мне нужно написать свою рекурсивную функцию. Я надеюсь, что шаблон <class T> int bindary_search (const T & item) должен быть добавлен в следующую версию C++.
std :: lower_bound () :)
OP: "пока что lower_bound и upper_bound терпят неудачу, потому что ..."
Таких функций нет, но можно написать простую, используя 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), который возвращает итератор для данного элемента. Однако ваши требования могут быть несовместимы с использованием набора (например, если вам нужно сохранить один и тот же элемент несколько раз).
да, это работает, и прямо сейчас у меня есть похожая реализация, однако это «наивная» реализация в том смысле, что она не использует контекст ситуации, в данном случае отсортированные данные.
Я не совсем понимаю ваш комментарий, поскольку lower_bound можно использовать только для отсортированных данных. Сложность ниже, чем при использовании find (см. Править).
извините, я забыл, что их нужно отсортировать, поэтому ваша реализация верна и использует отсортированные данные!
Чтобы дополнить ответ Люка, ознакомьтесь с классической статьей Мэтта Остерна Почему не следует использовать набор и что следует использовать вместо него (Отчет C++ 12: 4, апрель 2000 г.), чтобы понять, почему двоичный поиск с отсортированными векторами обычно предпочтительнее std :: set, который представляет собой ассоциативный контейнер на основе дерева.
Не используйте *i == val! Скорее используйте !(val < *i). Причина в том, что lower_bound использует <, а не == (т.е. T даже не требуется, чтобы быть сопоставимым по принципу равенства). (См. Эффективный STL Скотта Мейерса для объяснения разницы между равенство и эквивалентность.)
@gx, если мне нужен объект сравнения, это будет! comp (val, * i), верно?
В случае, если значение val, которое вы ищете, находится в конце индекса, хотя функция возвращает правильное значение, комментарий «не найден» становится неверным.
@ CanKavaklıoğlu Нет элемента, расположенного по адресу end. Диапазоны в стандартной библиотеке C++ представлены полуоткрытыми интервалами: конечный итератор «указывает» после на последний элемент. Таким образом, он может быть возвращен алгоритмами, чтобы указать, что значение не найдено.
Я бы сделал последний параметр T& val или const T& val. Соответствует вызову std и, конечно же, сохраняет копию.
@Halfgaar Вы даже можете сделать последний параметр boost::call_traits<T>::param_type, чтобы избежать ссылки на небольшие встроенные типы.
@LucTouraille Не будет ли он возвращать местоположение, которого не существует, если оно не найдено. Если у нас есть 5 элементов, return end выдаст 5-е местоположение, которого не существует.
@AaghazHussain Вот как алгоритмы стандартной библиотеки обозначают тот факт, что ни один элемент не был найден, путем возврата итератора в конец диапазона. Чтобы узнать, был ли элемент найден функцией binary_find, вы должны сравнить результат с концом: auto it = binary_find(v.begin(), v.end(), value); if (it != v.end()) { // value found, accessible at *it }
Просто комментарий, используя эту функцию, вам нужно будет провести еще одно сравнение после lower_bound. Если сравнение стоит дорого, возможно, лучше будет выполнить собственный двоичный поиск?
Так и должно быть в стандартной библиотеке!
Отметьте эту функцию, qBinaryFind:
RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )Performs a binary search of the range [begin, end) and returns the position of an occurrence of value. If there are no occurrences of value, returns end.
The items in the range [begin, end) must be sorted in ascending order; see qSort().
If there are many occurrences of the same value, any one of them could be returned. Use qLowerBound() or qUpperBound() if you need finer control.
Example:
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.
К сожалению, этот алгоритм несовместим с контейнерами STL.
Если std :: lower_bound слишком низкоуровневый, по вашему мнению, вы можете проверить boost :: container :: flat_multiset. Это прямая замена std :: multiset, реализованная как отсортированный вектор с использованием двоичного поиска.
Хорошая ссылка; а также хорошая ссылка в ссылка: lafstern.org/matt/col1.pdf, которая описывает, как поиск, реализованный с помощью отсортированного вектора, а не установленного (хотя оба являются log (N)), имеют более высокие константы пропорциональности существенно и ~ в два раза быстрее (недостаток заключается в том, что большее время ВСТАВКИ).
Решение, возвращающее позицию внутри диапазона, может быть таким, используя только операции с итераторами (оно должно работать, даже если итератор не арифметический):
template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{
const InputIterator beginIt = first;
InputIterator element = first;
size_t p = 0;
size_t shift = 0;
while((first <= last))
{
p = std::distance(beginIt, first);
size_t u = std::distance(beginIt, last);
size_t m = p + (u-p)/2; // overflow safe (p+u)/2
std::advance(element, m - shift);
shift = m;
if (*element == val)
return m; // value found at position m
if (val > *element)
first = element++;
else
last = element--;
}
// if you are here the value is not present in the list,
// however if there are the value should be at position u
// (here p==u)
return p;
}
int BinarySearch(vector<int> array,int var)
{
//array should be sorted in ascending order in this case
int start=0;
int end=array.size()-1;
while(start<=end){
int mid=(start+end)/2;
if (array[mid]==var){
return mid;
}
else if (var<array[mid]){
end=mid-1;
}
else{
start=mid+1;
}
}
return 0;
}
Пример: рассмотрим массив, A = [1,2,3,4,5,6,7,8,9] Предположим, вы хотите выполнить поиск по индексу 3 Изначально start = 0 и end = 9-1 = 8 Теперь, поскольку start <= end; mid = 4; (массив [середина], который равен 5)! = 3 Теперь 3 лежит слева от середины, так как она меньше 5. Следовательно, мы ищем только левую часть массива. Следовательно, теперь start = 0 и end = 3; mid = 2. Так как array [mid] == 3, значит, мы получили число, которое искали. Следовательно, мы возвращаем его индекс, равный mid.
Иметь код - это хорошо, но вы можете улучшить ответ, кратко объяснив, как он работает, для людей, которые плохо знакомы с языком.
Кто-нибудь неправильно отметил ваш пост как некачественный. А только кодовый ответ не является некачественным. Пытается ли он ответить на вопрос? Если нет, отметьте как «не отвечает» или порекомендуйте удалить (если в очереди на просмотр). б) Это технически некорректно? Проголосуйте против или оставьте комментарий.
Не уверен, как это соотносится с фактическим временем выполнения с решением std: lower_bound, но лично я предпочитаю это красивое и удобочитаемое решение. Это чистая и простая реализация двоичного поиска, возвращающая индекс. Понятия не имею, почему это так плохо оценено !! И да, это не шаблон, и да, он не возвращает итератор, но нужно ли нам проводить опрос, сколько людей выполняют бинарный поиск по чему-либо, кроме вектора целых чисел?
Самая короткая реализация, интересно, почему ее нет в стандартной библиотеке:
template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp = {})
{
// Note: BOTH type T and the type after ForwardIt is dereferenced
// must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
// This is stricter than lower_bound requirement (see above)
first = std::lower_bound(first, last, value, comp);
return first != last && !comp(value, *first) ? first : last;
}
От https://en.cppreference.com/w/cpp/algorithm/lower_bound
Я могу придумать две причины, по которым этого нет в стандартной библиотеке: они думают, что это легко реализовать, но основная причина, вероятно, в том, что для этого может потребоваться обратная версия operator () (), если сначала значение не взаимозаменяемо с *.
Что касается редактирования: вот почему std :: equal_range - это решение. В противном случае вам придется проверить равенство (или эквивалентность больше)