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

АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА

Этот алгоритм решает задачу поиска в списке некоторо­го заданного значения. Он позволяет установить, есть ли заданное значение в списке. Если это значение в списке присутствует, поиск будет считаться успешным, в противном случае - неудачным.

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

procedure Поиск (<список>, <искомое значение>) if (список пуст)

then (объявить поиск неудачным)

else

(выбрать как <проверяемое значение> первый

элемент списка)

while (<искомое значение> > <проверяемое значение> и есть непроверенные элементы) do (выбрать следующий элемент списка как <проверяемое значение>) if (<искомое значение> = <проверяемое значение>)

then (объявить поиск успешным) else (объявить поиск неудачным)

По окончании выполнения структуры while искомое значение либо будет найдено, либо выяснится, что его нет в списке. В любом случае успешность поиска можно установить, сравнивая искомое значение с проверяемым. Если они эквивалентны, поиск объявля­ется успешным. Для полной уверенности в правильности програм­мы она помещается в предложение else инструкции if.

Такая процедура позволяет установить, является ли кто-то пас­сажиром некоторого рейса, или установить, входит ли сахар в пе­речень ингредиентов некоторого блюда.

Таким образом, алгоритм последовательно рассматривает все элементы списка. В силу своей простоты он часто применяется к коротким спискам или когда это необходимо. Однако в случае длинных списков этот метод оказывается менее эффективным, чем другие.

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

Реализовать эту стратегию можно с помощью следующего алго­ритма, в котором учитывается возможность получения пустого списка.

procedure Search (<список>, <искомое_значение>) if (<список> пуст)

then (Объявить поиск неудачным)

else

(Выбрать "средний" элемент в <список> в качестве

<проверяемый_элемент>)

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

Case 1: <искомое_значение> = <проверяемый_элемент> (Объявить поиск успешным)

Case 2: <искомое_значение> < <проверяемый_элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, предшествующей элементу <проверяемый элемент>, элемент <искомое_значение>, и if (тот поиск успешен

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным) Case 3: <искомое_значение> > <проверяемый__элемент> (Применить процедуру Search, чтобы определить, есть ли в части списка, следующей за элементом <проверяемый_элемент>, элемент <искомое_значение> и if (тот поиск успешен)

then (Объявить этот поиск успешным) else (Объявить этот поиск неудачным)

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

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

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

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

Дата добавления: 2014-12-16