АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
4.4. Краткая теория
Поиск – это действие наиболее часто встречающееся в программировании. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных по мере их появления. Существует несколько основных "вариаций этой темы", и для них создано много различных алгоритмов. При дальнейшем рассмотрении мы исходим из такого принципиального допущения: группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Будем считать, что множество из N элементов задано, скажем, в виде такого массива
a: ARRAY[0..N-1] OF item
Обычно тип item описывает запись с некоторым полем, выполняющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному "аргументу поиска" x. Полученный в результате индекс i, удовлетворяющий условию a[i].key=x, обеспечивает доступ к другим полям обнаруженного элемента. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, то мы будем считать, что тип item включает только ключ, т.е. он есть ключ (key).
Линейный поиск
Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т.е. a[i] = x.
2. Весь массив просмотрен и совпадения не обнаружено.
Это дает нам линейный алгоритм:
i := 0;
WHILE (i < N) AND (a[i] <> x) DO
i := i+1 ;
END;
Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:
(0 £ i < N) AND (Ak : 0 £ k < i : ak ¹ x)
Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие его окончания:
((i = N) OR (ai = x)) AND (Ak : 0 £ k < i : ak ¹ x)
Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.
Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск ?
Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент "барьером", ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:
a: ARRAY[0..N] OF INTEGER
и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N] := x;
i := 0;
WHILE a[i] <> x DO
i := i+1;
END;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(ai=x) AND (Ak : 0 £ k < i : ak ¹ x)
Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.
Поиск делением пополам (двоичный поиск).
Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Вообразите себе телефонный справочник, в котором фамилии не будут расположены по порядку. Это нечто совершенно бесполезное! Поэтому мы приводим алгоритм, основанный на знании того, что массив а упорядочен, т.е. удовлетворяет условию
Ak : 1£ k < N : ak-1 ¹ ak
Основная идея - выбрать случайно некоторый элемент, предположим a[m], и сравнить его с аргументом поиска 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;
ENDIF;
ENDWHILE;
Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:
(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 совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.
Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания закончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log N. Быстрый алгоритм основан на следующем инварианте:
(Ak : 0 £ k < L : ak < x) AND (Ak : R £ k < N : ak ³ x)
причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.
L := 0;
R := N;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1
ELSE R := m ;
END
END
Условие окончания - L < R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L < m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.
Еще одним вариантом убыстрения поиска в случае упорядоченности данных является индексно-последовательный поиск. При таком поиске организуется две таблицы: таблица данных со своими ключами - упорядоченных по возрастанию, и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал. Другими словами, при прохождении упорядоченной таблицы мы сравниваем с ключом элементы не последовательно, а через определенный интервал, то есть задаем некоторый шаг поиска. Когда на очередном шаге поиска предыдущий элемент меньше значения ключа, а следующий элемент больше значения ключа, то устанавливаются соответственно нижняя low (kind<key) и верхняя hi (kind>key) границы в основной таблице. Между этими границами по основной таблице будет соответственно произвен уже обычный последовательный поиск.
Таблицы индексно-последовательного поиска
В псевдокоде алгоритм индексно-последовательного поиска следующий:
i = 1
while (i <= m) and (kind(i) <= key) do
i=i+1
endwhile
if i = 1 then low = 1
else low = pind(i-1)
endif
if i = m+1 then hi = n
else hi = pind(i)-1
endif
for j = low to hi
if key = k(j) then
search = j
return
endif
next j
search = 0
return
Эффективность данного вида поиска величина
.
Данный вид поиска, также как и бинарный, может давать значительный эффект при больших размерах таблиц поиска. Рекомендованный шаг для n элементов таблице – приблизительно
.
В принципе, для достижения наибольшей эффективности поиска при решении конкретных задач пользователь может задавать какой угодно шаг.