Быстрый последовательный список

Этот метод поиска является небольшим усовершенствованием предыдущего. В любой программе, имеющей циклы, наибольший интерес представляет оптимизация именно циклов, то есть сокращение числа действий в них. Посмотрим на алгоритм линейного поиска (программу раздела 2.1.). В цикле while производится два сравнения: (i<=n) и (A[i]<>Key). Избавимся от одного из них (от первого), положив A[n+1]:= Key. Тогда программа поиска будет выглядеть так:

A[n+1]:= Key;i:= 1;while A[i]<>Key do Inc(i);if i<=n then<элемент найден>else<элемент не найден>;

Надо сказать, что хотя такой фрагмент кода будет работать быстрее, но его теоретическая сложность остается такой же – T(n). Гораздо больший интерес представляют методы, не только работающие быстро, но и дающие лучшую теоретическую сложность. Один из таких методов – дихотомический поиск.

Дихотомический (бинарный) поиск

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

Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.

На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

Запишем все сказанное в виде программы:

l:= 1; r:= n;while (l<>r) dobeginm:= (l+r) div 2;if Key>A[m] then l:= m+1 else r:= m;end;if A[l]=Keythen<элемент найден>else<элемент не найден>;

Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).

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

Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива:

i:= n;while (i>=1)and(A[i]>Key) dobeginA[i+1]:= A[i]; {сдвигаем}Dec(i);end;A[i+1]:= Key;Inc(n);

Такая операция добавления имеет сложность T(n).

Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.

 

Интерполяционный поиск

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

Пусть имеется область поиска (l, r). Предположим, что элементы множества – целые числа, возрастающие в арифметической прогрессии. Тогда искомый элемент должен находится в массиве (если он вообще там есть) под индексом

(Это следует из свойств арифметической прогрессии)

В этом элементе и будем брать пробу.

l:= 1; r:= n;while (l<>r) dobeginm:= l+(r-l)*(Key-A[l])/(A[r]-A[l]);if Key>A[m] then l:= m+1 else r:= m;end;if A[l]=Keythen<элемент найден>else<элемент не найден>;

Мы сделали очень большое допущение, предположив, что элементы массива представляют собой возрастающую арифметическую прогрессию. В реальности такая ситуация встречается редко. Но этот метод хорошо работает для любых пусть не идеально, но более-менее равномерно распределенных данных. Если же мы имеем дело с неравномерно распределенными данными, то интерполяционный поиск может увеличить число шагов по сравнению с дихотомическим поиском. Теоретическая сложность интерполяционного поиска – T(log(log(n))). Это, конечно, лучше, чем сложность дихотомического поиска, но эти преимущества становятся достаточно заметными лишь при очень больших значениях n. Практически на всех реальных n разница между дихотомическим и интерполяционным поиском по скорости не существенна.

Добавление и удаление можно реализовать так же, как при дихотомическом поиске. К этим операциям предъявляется то же требование: они должны сохранять массива отсортированным.