Алгоритмы поиска.

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

Алгоритм двоичного поиска.Если массив упорядочен, то тогда можно использовать алгоритм бинарного (двоичного) поиска. По результату сравнения искомого значения со средним элементом массива из рассмотрения исключают первую или вторую половину списка, в зависимости от того больше или меньше «средний» (находящийся в середине списка) элемент искомого элемента. Для поиска в оставшейся части списка его тоже разбивают на две части и процедура повторяется. Таким образом, метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента. Общее количество сравнений пропорционально log₂N.

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

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

Рекурсивные системы представляют собой циклические процессы и зависят от правильного управления ими. Их работа зависит от проверки условия завершения (для двоичного поиска – пустой список или найденное значение) и правильного их построения, которое обеспечивает выполнение этого условия завершения. [1, 10]