уравнения одной переменной последовательным делением интервала пополам. В решении задачи 9 из гл. 10 выбирается случайный элемент, осуществляется разбиение, а потом выполняется рекурсия для всех элементов по одну сторону от этого элемента, что называется рандомизированным двоичным поиском. Двоичный поиск применяется также для древовидных структур данных, в алгоритмах сортировки карт (в которых используется соответствующая десятичная сортировка) и отладке программ (если программа "тихо угасла", куда вставить операторы печати, чтобы локализовать неверный оператор?). В каждом из этих примеров представление о программе как о совокупности небольших надстроек на фундаменте основного алгоритма двоичного поиска может натолкнуть программиста на это всемогущее ага!
2.3. СИЛА ПРИМИТИВОВ
Двоичный поиск - это решение, подходящее для многих задач; теперь рассмотрим задачу, имеющую несколько решений. Задача Б состоит в циклическом сдвиге вектора X из N элементов влево на I позиций за время, пропорциональное N, и с использованием только нескольких дополнительных слов памяти. В различных приложениях эта задача имеет разный вид: в таких языках программирования, как APL, циклический сдвиг обеспечивается как примитивная операция над векторами. В работе "Программные средства на Паскале"(с. 194, 195) в своей реализации редактора текста Керниган и Плоджер используют программу циклического сдвига. Ограничения на время и память важны в обоих указанных приложениях.
Можно попытаться решить эту задачу, копируя первые I элементов из вектора X во временный вектор, сдвигая оставшиеся N - I элементов влево на I позиций и копируя потом первые I элементов из временного вектора обратно на последние позиции в вектор X. Однако I дополнительных слов ОЗУ, используемые этой схемой, делают ее слишком дорогой с точки зрения памяти. При другом подходе мы могли бы написать подпрограмму для циклического сдвига вектора X влево на одну позицию (за время, пропорциональное N) и вызвать ее N раз, но это слишком расточительно по времени.
Для решения данной задачи при ограничениях на ресурсы, по всей вероятности, требуется более сложная программа. Один из успешных подходов осуществляется с помощью изящного трюка: поместить элемент Х[1] во временную ячейку Т, а потом перемещать элементы X [I + 1] в X [1], X [21 + 1] в X [I + 1] и т. д. (беря все индексы вектора X по модулю N) до тех пор, пока не вернемся к элементу X [1], вместо которого в этот момент мы подставим элемент из Т и остановим процесс.
