Стенли Липпман - Язык программирования C++. Пятое издание

Используя итераторы, двоичный поиск можно реализовать следующим образом:

// текст должен быть отсортирован

// beg и end ограничивают диапазон, в котором осуществляется поиск

auto beg = text.begin(), end = text.end();

auto mid = text.begin() + (end - beg)/2; // исходная середина

// пока еще есть элементы и искомый не найден

while (mid != end && *mid != sought) {

if (sought < *mid) // находится ли искомый элемент в первой половине?

end = mid; // если да, то изменить диапазон, игнорируя вторую

// половину

else // искомый элемент во второй половине

beg = mid + 1; // начать поиск с элемента сразу после середины

mid = beg + (end - beg)/2; // новая середина

}

Код начинается с определения трех итераторов: begбудет первым элементом в диапазоне, end— элементом после последнего, a mid— ближайшим к середине. Инициализируем эти итераторы значениями, охватывающими весь диапазон вектора vectorпо имени text.

Сначала цикл проверяет, не пуст ли диапазон. Если значение итератора mid равно текущему значению итератора end, то элементы для поиска исчерпаны. В таком случае условие ложно и цикл whileзавершается. В противном случае итератор midуказывает на элемент, который проверяется на соответствие искомому. Если это так, то цикл завершается.

Если элементы все еще есть, код в цикле whileкорректирует диапазон, перемещая итератор endили beg. Если обозначенный итератором midэлемент больше, чем sought, то если искомый элемент и есть в векторе, он находится перед элементом, обозначенным итератором mid. Поэтому можно игнорировать элементы после середины, что мы и делаем, присваивая значение итератора midитератору end. Если значение *midменьше, чем sought, элемент должен быть в диапазоне элементов после обозначенного итератором mid. В данном случае диапазон корректируется присвоением итератору begпозиции сразу после той, на которую указывает итератор mid. Уже известно, что midне указывает на искомый элемент, поэтому его можно исключить из диапазона.

В конце цикла whileитератор midбудет равен итератору endлибо будет указывать на искомый элемент. Если итератор midравен end, то искомого элемента нет в векторе text.

Упражнение 3.24. Переделайте последнее упражнение раздела 3.3.3 с использованием итераторов.

Упражнение 3.25. Перепишите программу кластеризации оценок из раздела 3.3.3 с использованием итераторов вместо индексации.

Упражнение 3.26. Почему в программе двоичного поиска использован код mid = beg + (end - beg) / 2;, а не mid = (beg + end) / 2;?

Массив (array) — это структура данных, подобная библиотечному типу vector(см. раздел 3.3), но с другим соотношением между производительностью и гибкостью. Как и вектор, массив является контейнером безымянных объектов одинакового типа, к которым обращаются по позиции. В отличие от вектора, массивы имеют фиксированный размер; добавлять элементы к массиву нельзя. Поскольку размеры массивов постоянны, они иногда обеспечивают лучшую производительность во время выполнения приложений. Но это преимущество приобретается за счет потери гибкости.

Если вы не знаете точно, сколько элементов необходимо, используйте вектор.

Массив является составным типом (см. раздел 2.3). Оператор объявления массива имеет форму a[d], где а— имя; d— размерность определяемого массива. Размерность задает количество элементов массива, она должна быть больше нуля. Количество элементов — это часть типа массива, поэтому она должна быть известна на момент компиляции. Следовательно, размерность должна быть константным выражением (см. раздел 2.4.4).

unsigned cnt = 42; // неконстантное выражение

constexpr unsigned sz = 42; // константное выражение

// constexpr см. p. 2.4.4

int arr[10]; // массив десяти целых чисел

int *parr[sz]; // массив 42 указателей на int

string bad[cnt]; // ошибка: cnt неконстантное выражение

string strs[get_size()]; // ok, если get_size - constexpr,

// в противном случае - ошибка