Где я могу получить "полезный" алгоритм бинарного поиска С++?

Мне нужен алгоритм двоичного поиска, который совместим с контейнерами 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.

Ответы

Ответ 1

Нет таких функций, но вы можете написать простой, используя 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), который возвращает итератор в данный элемент. Однако ваши требования могут быть несовместимы с использованием набора (например, если вам нужно хранить один и тот же элемент несколько раз).

Ответ 2

Вы должны посмотреть std::equal_range. Он вернет пару итераторов в диапазон всех результатов.

Ответ 3

Существует множество из них:

http://www.sgi.com/tech/stl/table_of_contents.html

Искать:

Отдельное примечание:

Вероятно, они думали, что поиск контейнеров может привести к нескольким результатам. Но в странный случай, когда вам просто нужно проверить существование, оптимизированная версия также будет приятной.

Ответ 4

Если std:: lower_bound слишком низкоуровневый по своему вкусу, вы можете проверить boost:: container:: flat_multiset. Это замена для замены std:: multiset как отсортированного вектора, использующего двоичный поиск.

Ответ 5

std:: lower_bound():)

Ответ 6

Проверьте эту функцию, qBinaryFind:

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Выполняет двоичный поиск диапазона [begin, end] и возвращает позицию возникновения стоимости. Если здесь не являются значениями стоимости, возвращается конец.

Элементы в диапазоне [начало, конец) должны сортироваться в порядке возрастания; видеть 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.

Ответ 7

Решение, возвращающее позицию внутри диапазона, может быть таким, используя только операции с итераторами (он должен работать, даже если итератор не арифметичен):

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)/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;

}