Структуры и алгоритмы обработки данных


Поиск делением пополам (двоичный поиск)


Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Поэтому приведем алгоритм (он называется поиском делением пополам¦), основанный на знании того, что массив A упорядочен, т. е. удовлетворяет условию

pic2_03.jpg (4820 bytes)

Основная идея v выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то делается вывод, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Выбор m совершенно не влияет на корректность алгоритма, но влияет на его эффективность. Очевидно, что чем большее количество элементов исключается на каждом шаге алгоритма, тем этот алгоритм эффективнее. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива.

pic2_1.jpg (16009 bytes)

Рис.2.1. Поиск делением пополам

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

Алгоритм 2.

L:=0; R:=N-1; Found:=false;

while(L<=R) and not Found do begin

m:=(L+R) div 2;

                          if a[m]=x then begin

                                       Found:=true

                         end else begin

                                if a[m]<x then L:=m+1 else R:=m-1




Начало  Назад  Вперед



Книжный магазин