23. Последовательный поиск в упорядоченном и неупорядоченном списке. Дихотомический поиск в упорядоченном массиве. Временная сложность алгоритмов

 

В этом параграфе полагаем, что СД, в которой ведется поиск, - это множество, которое представлено либо линейным списком, либо массивом.

 

1.1. Поиск в неупорядоченном множестве

Если множество представлено стеком, очередью или деком, то его элементы весьма затруднительно расположить в порядке возрастания ключей; поэтому алгоритм поиска требует одного просмотра списка. Для определенности будем считать, что СД - это очередь и доступ к ней осуществляется через указатель head на головной элемент очереди.

                       

l:= head; b:= true;

while (l <> nil) and (l^.key <> y) do

            l:= l^.ptr;

if l <> nil then s:= l^.info else b:= false;

                       

Вторая компонента проверки условия продолжения цикла не вычисляется, если первая имеет значение “false”.

Если в очереди хранится n элементов, то в худшем случае, когда элемент с данным ключом в множестве отсутствует, цикл выполняется n раз (условие цикла – n+1 раз) и, таким образом, Tmax(n)=O(n).

 

1.2. Последовательный поиск в упорядоченном множестве

Можно улучшить предыдущий алгоритм, если в типе key задано отношение порядка и структура данных построена так, что всегда, когда элемент a предшествует элементу b, ключ элемента a меньше ключа элемента b. Использование отношения порядка существенно облегчает поиск, так как даже в случае отсутствия искомого элемента нет необходимости систематически добираться до конца множества - достаточно “добраться” до первого встретившегося элемента с ключом, превосходящим y.

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

Будем полагать, что доступ к списку с двумя связями осуществляется через указатель left на крайний слева элемент очереди.

                       

l:= left; b:= true;

while (l <> nil) and (l^.key < y) do  

            l:= l^.ptr;

if (l <> nil) and (l^.key = y) then s:= l^.info else b:= false;

Оценим кол-во проверок условия цикла в случае, когда искомый элемент отсутствует в списке:

            если y < a[1].key, то будет проведено       1 сравнение,

            если a[1].key < y < a[2].key -                       2 сравнения,

            если a[n-1].key< y < a[n].key -                     n сравнений,

            если y > a[n].key -                                        тоже    n сравнений.

            Найдем среднее число проверок цикла как отношение общего числа всех сравнений к общему числу всех случаев: (1+2+…+(n-1)+n+n) / (n+1) = n(n+3)/(2n+2) ~ n/2.

Напомним, что для неупорядоченной таблицы это значение было в 2 раза больше.

 

1.3. Дихотомический поиск в упорядоченном множестве

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

            Идея этого метода проста: сравнивая ключ искомого элемента с ключом элемента в середине массива, мы узнаем, в какой половине (левой или правой) следует продолжать поиск. После этого алгоритм рекурсивно применяется к левой и правой части массива до получения массива из одного элемента.

            Приведенная на рис. 2.2. процедура locate осуществляет дихотомический поиск записи с заданным ключом. Вызов процедуры осуществляется оператором “locate(1,n);”. Логическая переменная b принимает значение true, если искомый элемент в массиве найден.

procedure locate(first,last:integer);

var m: integer;

 begin

    if first<last then

       begin

           m:= (first+last) div 2;

           if x<a[m].key then locate(first,m)

           else if x>a[m].key then locate(m+1,last)

                  else {* x=a[m].key *} begin s:=a[m].info; b:=true end

        end

    else

       begin if x=a[first].key then begin s:=a[first].info; b:=true end end

 end; {*locate*}

            Рис. 2.2. Процедура дихотомического поиска.

 

            Полное дерево сравнений, для массива, состоящего из n элементов, содержит ровно n концевых вершин. На рис. 2.3 приведено полное дерево сравнений для массива, имеющего 5

            Рис. 2.3. Дерево сравнений

элементов.     В §8 главы I было доказано, что если бинарное дерево с максимальным количеством вершин имеет n концевых вершин, то его высоту m можно найти по формуле (1.1):

 m=log2(n).

Поскольку полное дерево сравнений не обязательно содержит максимальное количество вершин, то это равенство при больших n выполняется приближенно: m~log2(n). А так как именно высота m определяет максимальную сложность этого алгоритма, то T(n)=O(log2n).

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