А.2.3. Алгоритмы бинарного поиска

Хотя эти алгоритмы можно использовать с прямыми итераторами, они обладают специализированными версиями, которые работают с итераторами прямого доступа и выполняются гораздо быстрей.

Этим алгоритмам требуются прямые итераторы, но они оптимизированы так, что выполняются намного быстрее, если вызываются с итераторами прямого доступа. С технической точки зрения, независимо от типа итератора, эти алгоритмы выполняют логарифмическое количество сравнений. Но при использовании с прямыми итераторами они должны выполнить линейное количество операций с итераторами для перебора элементов последовательности.

Эти алгоритмы требуют, чтобы элементы в исходной последовательности уже были упорядочены. Эти алгоритмы ведут себя подобно одноименным функциям-членам ассоциативных контейнеров (см. раздел 11.3.5).

Алгоритмы equal_range(), lower_bound() и upper_bound() возвращают итераторы на позиции последовательности, куда мог бы быть вставлен заданный элемент при сохранении существующего порядка в последовательности. Если элемент больше всех остальных в последовательности, то возвращаемый итератор будет итератором после конца.

Каждый алгоритм предоставлен в двух версиях: первая использует для проверки элементов оператор меньше (<) типа элемента, а вторая использует заданную функцию сравнения. В следующих алгоритмах "x меньше, чем y" означает, что выражения x<y и comp(x, y) истинны:

lower_bound(beg, end, val)

lower_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого больше или равно значению val, или итератор end, если такого элемента нет.

upper_bound(beg, end, val)

upper_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого меньше значения val, или итератор end, если такого элемента нет.

equal_range(beg, end, val)

equal_range(beg, end, val, comp)

Возвращает пару (см. раздел 11.2.3), член first которой является итератором, возвращаемым функцией lower_bound(), а член second — итератором, возвращаемым функцией upper_bound().

binary_search(beg, end, val)

binary_search(beg, end, val, comp)

Возвращает логическое значение, свидетельствующее о наличии в последовательности элемента, значение которого равно val. Два значения, x и y, считаются равными, если x не меньше y и y не меньше x.

Более 800 000 книг и аудиокниг! 📚

Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением

ПОЛУЧИТЬ ПОДАРОК