Где я могу найти «полезный» алгоритм двоичного поиска C ++?

107

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

Роберт Гулд
источник
2
Что касается редактирования: вот почему std :: equal_range - это решение. В противном случае вам придется проверить равенство (или эквивалентность, чтобы быть больше),
Люк Эрмитт
Вы должны проверить равенство после использования (нижний / верхний) _bound (см. Ответ ниже).
Люк Турей,
В документации lower_bound и upper_bound указано, что диапазон должен быть отсортирован, и поэтому они могут быть реализованы как двоичный поиск.
vividos
@vividos, ура! вы нашли только ту часть документации, о которой мне нужно было знать! Спасибо!
Роберт Гулд,
Роберт, алгоритмы lower / upper_bound / equal_range не работают с несортированными диапазонами. Вам просто повезло увидеть, как они работают с выбранным вами образцом элементов.
Люк Эрмитт,

Ответы:

97

Таких функций нет, но вы можете написать простую, используя 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
}

Другое решение - использовать a std::set, который гарантирует упорядочение элементов и предоставляет метод, iterator find(T key)который возвращает итератор для данного элемента. Однако ваши требования могут быть несовместимы с использованием набора (например, если вам нужно сохранить один и тот же элемент несколько раз).

Люк Турель
источник
да, это работает, и прямо сейчас у меня есть похожая реализация, однако это «наивная» реализация в том смысле, что она не использует контекст ситуации, в данном случае отсортированные данные.
Роберт Гулд,
5
Я действительно не понимаю ваш комментарий, поскольку lower_bound можно использовать только для отсортированных данных. Сложность ниже, чем при использовании find (см. Править).
Люк Турей,
4
Чтобы дополнить ответ Люка, ознакомьтесь с классической статьей Мэтта Остерна « Почему не следует использовать набор и что следует использовать вместо него» (отчет C ++ 12: 4, апрель 2000 г.), чтобы понять, почему двоичный поиск с отсортированными векторами обычно предпочтительнее std :: set , который представляет собой ассоциативный контейнер на основе дерева.
ZunTzu 03
16
Не используйте *i == val! Скорее использовать !(val < *i). Причина в том, что lower_boundusing <, not ==(т.е. Tдаже не требуется, чтобы быть сопоставимым по равенству). (См. « Эффективный STL» Скотта Мейерса для объяснения разницы между равенством и эквивалентностью .)
gx_
1
@ CanKavaklıoğlu Нет элемента, расположенного в end. Диапазоны в стандартной библиотеке C ++ представлены с полуоткрытыми интервалами: конечный итератор «указывает» после последнего элемента. Таким образом, он может быть возвращен алгоритмами, чтобы указать, что значение не найдено.
Люк Турель
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 выполняются на непересекающихся интервалах (после некоторого ручного двоичного поиска). При этом, вероятно, это будет дороже, особенно для диапазонов с несколькими совпадающими значениями.
Matthieu M.
6

Их множество:

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

Ищи:

Отдельно отметим:

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

Мартин Йорк
источник
3
binary_search не возвращает итератор, как я упоминал ранее, поэтому я ищу альтернативу.
Роберт Гулд,
1
Да, я знаю. Но он вписывается в набор алгоритмов двоичного поиска. Так что другим приятно знать об этом.
Мартин Йорк,
8
binary_search просто, как и многие другие вещи в STL, назван неправильно. Я ненавижу это. Проверка существования - это не то же самое, что поиск чего-либо.
OregonGhost
2
Эти функции двоичного поиска бесполезны в случае, если вы хотите узнать индекс искомого элемента. Для этой задачи мне нужно написать свою рекурсивную функцию. Я надеюсь, что шаблон <class T> int bindary_search (const T & item) должен быть добавлен в следующую версию C ++.
Кемин Чжоу
3

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

ZunTzu
источник
1
Хорошая ссылка; а также хорошая ссылка в ссылке: lafstern.org/matt/col1.pdf , в которой описывается, как поиски, реализованные с помощью отсортированного вектора, а не набора (хотя оба являются log (N)), имеют значительно лучшие константы пропорциональности и ~ в два раза быстрее (недостатком является большее время ВСТАВКИ).
Дэн Ниссенбаум,
2

Самая короткая реализация, интересно, почему ее нет в стандартной библиотеке:

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

Trozen
источник
Я могу придумать две причины, по которым этого нет в стандартной библиотеке: они думают, что это легко реализовать, но основная причина, вероятно, в том, что может потребоваться обратная версия operator () (), если значение не является взаимозаменяемым с * первым.
user877329
1

Отметьте эту функцию, 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 .

Лаванд
источник
1
К сожалению, этот алгоритм несовместим с контейнерами STL.
bartolo-otrit
0

std :: lower_bound () :)

муги
источник
OP: «пока что lower_bound и upper_bound терпят неудачу, потому что ...»
underscore_d
0
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; (array [mid], который равен 5)! = 3 Теперь 3 лежит слева от mid, поскольку он меньше 5. Следовательно, мы ищем только левую часть массива. Следовательно, теперь start = 0 и end = 3; mid = 2. Так как array [mid] == 3, значит, мы получили число, которое искали. Следовательно, мы возвращаем его индекс, равный mid.

Сиддхарт Кумар Шукла
источник
1
Иметь код - это хорошо, но вы можете улучшить ответ, кратко объяснив, как он работает, для людей, которые плохо знакомы с языком.
Taegost
Кто-то ошибочно отметил ваше сообщение как некачественное . Ответ, состоящий только из кода, не является некачественным . Пытается ли он ответить на вопрос? Если нет, отметьте как «не ответ» или порекомендуйте удалить (если в очереди на просмотр). б) Это технически некорректно? Проголосуйте против или оставьте комментарий.
Вай Ха Ли,
0

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

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;

}
Микеле Белотти
источник