диапазон отсортирован. Программа ниже использует версии четырех алгоритмов без дополнительного аргумента-предиката:

bsearch.cpp: Двоичный поиск и родственные алгоритмы, ttinclude <iostream> ttinclude <algorithin> using namespace std;

int mainO

{ int a[10] = {3, 3, 5, 5, 5, 5, 5, 7, 8, 9}, *p, k; cout << Array a:\n ;

for (k=0; k<10; k++) cout к ; cout endl;

for (k=0; k<10; k++) cout a[k] ; cout endl;

p = lower bound(a, a+10, 5); cout p - a = << p - a

after p = lower bound(a, a+10, 5);\n ;

p = lower bound(a, a+10, 4); cout p - a = p - a

after p = lower bound(a, a+10, 4);\n ;

p = upper bound(a, a+10, 5); cout p - a = p - a

after p = upper bound(a, a+10, 5);\n ;

pair<int*, int*> P(0, 0); P = equal range(a, a+10, 5); cout

After P = equal range(a, a+10, 5) we have:\n ; cout P.first - a = P.first - a << endl; cout P.second - a = P.second - a endl;

bool b = binary search(a, a+10, 5); cout Results of binary search:\n ; cout 5 (b ? : not )

found in array a.\n ; b = binary search(a, a+10, 4); cout 4 (b ? : not )

<< found in array a.\n ; return 0;

В результате мы получаем такой вывод:

Array а:

0123456789 3 3 5 5 5 5 5 7 8 9

р - а = 2 after р = lower bound(a, а+10, 5)

р - а = 2 after р = lower bound(a, а+10, 4)

р - а = 7 after р = upper bound(a, а+10, 5) After Р = equal range(а, а+10, 5) we have:

P.first - a = 2

P.second - a = 7 Results of binary search: 5 found in array a. 4 not found in array a.

Как показывает этот вывод, алгоритм lowerbound возвращает итератор, ссылающийся на первую позицию, куда можно вставить заданный элемент без нарушения порядка сортировки. Для значений 4 и 5 это позиция а{2]. Аналогично вызов upperbound возвращает значение, указывающее, что а[1] является последней позицией, куда может быть поставлено значение 5 без нарушения сортировки.

Вызов equal range сообщает нам, что [2, 7) является диапазоном позиций, куда может быть вставлено значение 5. Если бы мы использовали вызов

Р = equal range(а, а+10, 4);

тогда значения обоих выражений P.first - а и Rsecond - а были бы равны 2, поскольку а[2] - единственная позиция, куда может быть добавлено значение 4.

Алгоритм binary search информирует нас, найдено ли искомое значение в диапазоне, но не сообщает, в какой позиции находится это значение, ни в какую позицию его можно добавить, если оно не найдено.

7.3.7. Объединение

Outputlterator merge

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result); Outputlterator merge

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result. Compare comp); void inplace merge

(Bidirectionallterator first, Bidirectionallterator middle, Bidirectionallterator last); void inplace merge

(Bidirectionallterator first, Bidirectionallterator middle, Bidirectionallterator last. Compare comp);

Существуют две версии алгоритма merge (объединить), одну из которых мы обсуждали в разделе 1.7. Другая версия имеет шестой аргумент, являющийся предикатом. Она может быть использована для объединения двух диапазонов, отсортированных в порядке убывания, как показывает следующая программа:

тег gel .срр: Объединение двух диапазонов,

отсортированных в нисходящем порядке.

♦include <iostream>

♦include <algorithm>

♦include <functional>

using namespace std;

int main()

{ int a[5] = {30, 28, 15, 13, 11}, b[4] = {25, 24, 15, 12}, c[9];

merge(a, a+5, b, b+4, c, greater<int>()); copy(c, c+9, ostream iterator<int>(cout, )); cout endl; return 0;

Эта программа выводит:

30 28 25 24 15 15 13 12 11

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

Если две отсортированные в восходящем порядке последовательности находятся в одном диапазоне {first, last), причем одна из них - {first, middle), а другая - [middle, last), мы можем использовать следующий вызов, чтобы объединить эти последовательности, так что диапазон [first, last) будет полностью отсортирован:

inplace merge(first, middle, last);

Приведенная ниже программа демонстрирует работу алгоритма inplacetnerge.

II inplace.cpp: Объединение двух

отсортированных поддиапазонов.

♦include <iostream>

♦include <algorithm>

using namespace std;

int main()

{ int a[7] = {2, 5, 8, /* Второй диапазон: */ 3, 4, 5, 9};