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



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


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

Ak : 1£ k < N : ak-1 ¹ ak

Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Это соображение приводит нас к следующему алгоритму (он называется "поиском делением пополам"). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L := 0;

R := N-1;

found := FALSE;

WHILE (L Ј R) AND NOT found DO

    m := любое значение между L и R;

    IF a[m] = x THEN found := TRUE;

    IF a[m] < x THEN L := m+1

    ELSE R := m-1;

    END;

END;

Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:

(L £ R) AND (Ak

: 0 £ k < L : ak < x) AND (Ak

: R < k < N : ak > x)

из чего выводится результат

found OR ((L > R) AND (Ak : 0 £ k < L : ak

< x) AND (Ak : R < k < N : ak > x))

откуда следует

(am = x) OR (Ak : 0 £ k < N : ak ¹ x)

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


Содержание  Назад  Вперед