сообщения, возросло на 0.3 мс, что в данном случае является очень большим скачком. Мы установили, что причина в том, что поиск осуществляется линейно, заметили прикладную программу, чтобы использовать двоичный поиск, и проблема была решена.
Но рассказ о двоичном поиске не заканчивается быстрым поиском в упорядоченном массиве. Р. Уил из компании Michael Backer Jr., Inc. применил этот метод для очистки колоды, содержащей примерно 10 000 перфокарт, от имеющейся в ней единственной плохой карты. К несчастью, о наличии плохой карты неизвестно заранее. О ней можно узнать, лишь прогнав подмножество карт через программу и получив бессмысленный ответ, а это занимает несколько минут. Предшественники Уила пытались обнаружить ошибку, пропуская за один раз по нескольку карт через программу и продвигалась к решению черепашьим шагом. Догадайтесь, каким образом Уил нашел подозреваемую карту только за десять прогонов программы?
После этой разминки мы можем энергично взяться за задачу А. Дана магнитная лента, содержащая в случайном порядке не более 1 млн. 20-битовых целых чисел, и мы должны найти одно 20-битовое число, отсутствующее на ленте. (Здесь должен быть хотя бы один пропуск, так как таких чисел всего 220 или 1 048 576.) Имея достаточный объем ОЗУ, мы могли бы использовать побитовое представление этих чисел (гл. 1), выделив 131 072 восьмибитовых слов. Однако в задаче также спрашивается о том, как найти пропущенное число, имея только несколько десятков слов в ОЗУ и несколько дополнительных лентопротяжек. Для определения того, в какой половине содержится пропущенный элемент, при использовании метода двоичного поиска, нужно найти область, представление элементов в области и метод зондирования. Как это сделать?
Областью будем считать последовательность чисел, в которой должен содержаться по крайней мере один пропущенный элемент, и пусть все эти числа записаны на магнитной ленте. Идея состоит в том, чтобы прозондировать область, подсчитав число элементов выше и ниже ее средней точки - либо в верхней, либо в нижней части области содержится не более половины элементов всей области. Так как в области нет одного элемента, то он отсутствует именно в меньшей половине. В этой задаче используется большая часть компонентов алгоритма двоичного поиска; попытайтесь сами скомпоновать их, прежде чем подсмотрите решение и увидите, как это сделал Э. Рейнгоулд.
Эти примеры использования двоичного поиска дают только поверхностное представление о его применении в программировании. В программе нахождения корня используется двоичный поиск для решения
23
