Алгоритм двоичного поиска

Обратимся снова к задаче поиска, или проверке, находится ли определенный элемент в упорядоченном списке. По на этот раз мы будем использовать метод, который мы применяем, когда ищем какое-либо слово в словаре. В таком случае мы не просматриваем весь список элемент за элементом или страница за страницей, а начинаем поиск, открывая словарь на странице, на которой предположительно могло бы находиться это слово. Если нам посчастливится, то мы сразу обнаружим нужное слово. В противном случае мы должны продолжать поиск. Но действуя таким образом, мы значительно сужаем поле поиска.

Конечно, когда мы ищем слово в словаре, мы располагаем знаниями о том, где оно вероятнее всего находится. Если мы ищем слово «сомнамбулизм», мы начнем поиск с той части словаря, которая ближе к концу. Однако в случае произвольных списков у нас нет такого преимущества, поэтому условимся всегда начинать поиск с элемента, находящегося в «середине» списка. Слово «середина» заключено в кавычки, потому что список может содержать четное количество элементов и, следовательно, его середины просто не существует. В таком случае будем принимать за «середину» последний элемент первой половины списка.

Если элемент, находящийся в середине списка, является искомым, то поиск признается успешным. В противном случае мы, по крайней мере, можем ограничить процесс поиска первой или второй половиной списка, в зависимости от того, больше или меньше искомый элемент, чем рассматриваемый элемент. (Не забывайте, что наш список упорядочен.)

Для поиска в оставшейся части списка можно применить последовательный поиск, но вместо этого воспользуемся тем же методом, который мы применяли к целому списку. То есть мы выбираем для рассмотрения элемент, находящийся в «середине» оставшейся части списка. Как и раньше, если этот элемент является искомым, то процесс поиска завершается. В противном случае мы можем свести поле поиска к части списка меньшего размера.

Процесс поиска записи John с помощью этого метода изображен на рис. 4.7. Сначала мы рассматриваем элемент Harry, находящийся в середине. Так так искомый элемент должен располагаться после этого элемента, то мы продолжаем поиск только в нижней половине исходного списка. В середине этого подсписка находится запись Larry. Так как искомая запись должна предшествовать данной, мы сосредотачиваем наше внимание на первой половине подсписка. Серединой этой части подсписка является искомый элемент John, следовательно, поиск успешно завершен. Говоря проще, наш метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента.

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

Эти идеи, записанные с помощью псевдокода, представлены в листинге 4.3. Согласно им, поиск следует начать с проверки того, не является ли список пустым. Если да, то поиск признается неудачным. В противном случае мы рассматриваем элемент, находящийся в середине списка. Если он не является искомым, мы продолжаем поиск или в первой, или во второй половине списка. Было бы неплохо при этом использовать абстрактный инструмент. В частности, в нашем случае мы применяем для выполнения дополнительного поиска процедуру Поиск. Следовательно, для того чтобы наша программа работала, мы должны создать такую процедуру.

Листинг 4.3. Принцип метода двоичного поиска

if (Список пустой) then

(сообщить, что поск неудачен.) else

[Назначить элемент, находящийся в середине Список, как ПроверяемоеЗначение; Выполнить набор команд, соответствующий одному из случаев: случай 1: ИскомоеЗначение = ПроверяемоеЗначение

(Поиск успешно завершен.) случай 2: ИскомоеЗначение < ПроверяемоеЗначение

(Поиск ИскомоеЗначение в части списка, расположенной до ПроверяемоеЗначение, и сообщить о результатах этого поиска.) случай 3: ИскомоеЗначение > ПроверяемоеЗначение

(Поиск ИскомоеЗначение в части списка, расположенной после ПроверяеноеЗначение, и сообщить о результатах этого поиска.) ] end if

Но эта процедура должна выполнять ту же задачу, которую мы только что записали с помощью псевдокода. Она сначала должна проверять, не является ли список пустым, и если нет — рассматривать элемент, находящийся в середине списка. Следовательно, мы можем получить необходимую процедуру, просто назвав текущую подпрограмму процедурой Поиск (листинг 4.4).

Листинг 4.4. Алгоритм двоичного поиска, записанный с помощью псевдокода

Procedure Поиск (Список. ИскомоеЗначение) if (Список пустой) then

(Признать поск неудачным.)

else

[Назначить элемент, находящийся в середине Список, как ПроверяемоеЗначение: Выполнить набор команд, соответствующий одному из случаев: случай 1: ИскомоеЗначение = ПроверяемоеЗначение

(Поиск успешно завершен.) случай 2: ИсконоеЗначение < ПроверяемоеЗначение

(Применить процедуру Поиск для обнаружения ИскомоеЗначение в части Список, предшествующей ПроверяемоеЗначение. и сообщить о результатах поиска.) случай 3: ИскоиоеЗначение > ПроверяемоеЗначение

(Применить процедуру Поиск для обнаружения ИскомоеЗначение в части Список, следующей за ПроверяемоеЗначение, и сообщить о результатах поиска.) ] end if

Обратите внимание на то, что эта процедура ссылается на саму себя. Когда мы выполняем эту процедуру и достигаем команды Применить процедуру Поиск..., мы должны будем применить ту же процедуру, которую мы использовали для целого списка, к списку меньшего размера. Если этот поиск оказывается успешным, то мы объявляем и первоначальный поиск успешным. Если же этот дополнительный поиск завершился неудачей, то мы объявляем исходный поиск безрезультатным.

РЕКУРСИВНЫЕ СТРУКТУРЫ В ИСКУССТВЕ

Следующую рекурсивную структуру можно применить к прямоугольному холсту, чтобы создать рисунок в стиле голландского художника Пита Мондриана (Piet Mondrian, 1872-1944), создававшего картины, в которых прямоугольный холст разделялся на прямоугольники меньшего размера. Попробуйте выполнить эту процедуру, чтобы создать рисунок, подобный изображенному. Начните с применения этой процедуры к прямоугольнику, представляющему рабочий холст.

procedure Mondrian (Прямоугольник)

if (Прямоугольник слишком большой на ваш «художественный» взгляд) then (разделить Прямоугольник на два прямоугольника меньшего размера;

применить процедуру Mondrian к одному из прямоугольников; ________применить процедуру Mondrian к другому прямоугольнику).

Для того чтобы проследить, как процедура (см. листинг 4.4) выполняет задачу, рассмотрим процесс поиска имени Bill в списке Alice, Bill, Carol, David, Evelyn, Fred и George. Сначала мы выбираем для рассмотрения имя David (так как оно находится в середине нашего списка). Поскольку искомое имя Bill должно располагаться выше этого элемента, мы применяем процедуру Поиск к списку элементов, предшествующих имени David, то есть к списку Alice, Bill и Carol. Поступая так, мы создаем вторую копию процедуры поиска и назначаем ей выполнение этой дополнительной задачи.

Теперь в нашем распоряжении находятся две выполняемые копии процедуры поиска (рис. 4.8). Выполнение исходной процедуры временно приостанавливается на команде

Применить процедуру Поиск для обнаружения ИскомоеЗначение в части Список, предшествующей ПроверяемоеЗначение. и сообщить о результатах поиска.

в то время как мы используем вторую копию для поиска нужного элемента в списке Alice, Bill и Carol. Когда этот дополнительный поиск завершается, мы передаем его результаты исходной процедуре и продолжаем ее выполнение. Таким образом, вторая копия процедуры является вспомогательной по отношению к исходной процедуре. Она выполняет задачи, назначаемые ей исходным модулем, а затем исчезает.

В процессе дополнительного поиска рассматривается элемент Bill, поскольку он расположен в середине списка Alice, Bill и Carol. Так как он совпадает с искомым элементом, то поиск успешно завершается.

На этом этапе мы завершили дополнительный поиск, как предписывалось исходной процедурой, поэтому можно продолжить выполнение этой исходной копии, то есть объявить результат дополнительного поиска результатом первоначального поиска. Следовательно, поиск элемента Bill успешно завершен. В процессе поиска было правильно установлено, что имя Bill является элементом списка Alice, Bill, Carol, David, Evelyn, Fred и George.

Теперь рассмотрим, что произойдет, если мы будем использовать процедуру, приведенную в листинге 4.4, чтобы найти запись David в списке Alice, Carol, Evelyn, Fred и George. На этот раз исходная копия процедуры рассматривает элемент Evelyn и делает вывод, что искомая запись должна находиться в первой половине списка. Следовательно, она предписывает другой копии процедуры выполнить поиск имени в списке, состоящем из двух элементов, Alice и Carol (рис. 4.9).

Вторая копия процедуры выбирает для рассмотрения элемент Carol1 и делает вывод о том, что искомая запись должна находиться после этого элемента. Затем она предписывает третьей копии процедуры выполнить поиск имени в списке, который располагается после элемента Carol. Этот подсписок является пустым. Таким образом, третья копия процедуры должна искать имя David в пустом списке (рис. 4.10). Задача исходной копии процедуры состоит в том, чтобы найти нужный элемент в списке Alice, Carol, Evelyn, Fred и George, при этом рассматривается элемент Evelyn. Задача второй копии процедуры — найти нужный элемент в списке Alice и Carol; рассматривается элемент Carol. Третья копия собирается осуществлять процесс поиска в пустом списке.

Конечно, третья копия объявляет поиск неудачным. Завершение работы третьей копии позволяет второй копии продолжить выполнение своей задачи. Она обнаруживает, что затребованный поиск оказался безрезультатным, сообщает о том, что ее поиск является неудачным, и завершает работу. Это сообщение ожидает исходная процедура, поэтому теперь она может продолжить свою работу. Так как затребованный поиск закончился неудачей, она объявляет поиск, выполняемый ею самой, неудачным и завершается. Таким образом, наша программа сделала правильный вывод о том, что список Alice, Carol, Evelyn, Fred и George не содержит имени David. Возвращаясь к предыдущим примерам, можно заметить, что алгоритм, представленный в листинге 4.4, многократно делит список на части меньшего размера так, что при последующем поиске можно ограничиться только одной из этих двух частей. Именно поэтому этот алгоритм и называется алгоритмом двоичного поиска.