Линейный
поиск
Пусть
дан массив элементов A и ключ b. Для
b необходимо найти совпадающий с
ним элемент массива А. Линейный
поиск подразумевает
последовательный просмотр всех
элементов массива А в порядке их
расположения, пока не найдется
элемент равный b. Если заранее
неизвестно, имеется данный
элемент в массиве или нет, то
необходимо следить за тем, чтобы
поиск не вышел за границы массива,
что достигается использованием
стоппера (барьерного элемента).
Рассмотрим 2 примера:
1)без
использования стоппера
const
N=10;
type
Any=integer;
var
A:array[0..N-1] of Any;
i:integer;
b:Any;
begin
writeln('Введите элементы массива:');
for i:=0 to N-1 do
readln(A[i]);
write('Введите ключ:');
readln(b);
i:=0;
while (i<>N) and (A[i]<>b) do
i:=i+1;
if i<>N then
writeln('Элемент, совпадающих с
ключом, найден. Позиция элемента
-',i+1)
else
writeln('Элементов,
совпадающих с ключом, нет');
end.
2)
с использованием стоппера
const
N=11;
type
Any=integer;
var
A:array[0..N] of Any;
i:integer;
b:Any;
begin
writeln('Введите элементы массива:');
for i:=0 to N-1 do
readln(A[i]);
write('Введите ключ:');
readln(b);
A[N]:=b; {стоппер}
i:=0;
while A[i]<>b do
i:=i+1;
if i<>N then
writeln('Элемент, совпадающих с
ключом, найден. Позиция элемента
-',i+1)
else
writeln('Элементов,
совпадающих с ключом, нет');
end.
Следует отметить, что в общем
случае при линейном поиске среди N
элементов требуется в среднем N/2
сравнений в случае успешного
поиска и N сравнений в наихудшем
случае, и затраты времени для
больших массивов поэтому велики.
Применяется данный алгоритм, если
никакой дополнительной
информации о данных массива нет.
Бинарный
поиск
Очевидно, что нельзя каким-либо
способом ускорить поиск, если
отсутствует информация о данных,
среди которых производится поиск.
Также известно, что если данные
упорядочены, то поиск можно
сделать значительно эффективнее.
Поэтому рассмотрим алгоритм,
который основан на том, что массив
A упорядочен (т. е. a[i-1]<=a[i] при 1<=i<N).
Суть: берут средний элемент
массива и сравнивают его с ключом.
В результате возможны 3 случая:
1)
если элемент массива равен ключу,
то искомый элемент найден;
2)если
элемент массива меньше ключа, то
все элементы массива с индексами,
которые меньше N/2 исключаются из
рассмотрения;
3)если
элемент массива больше ключа, то
все элементы массива с индексами,
которые больше N/2 исключаются из
рассмотрения;
Затем поиск продолжается в одной
из половин массива аналогичным
образом.
const
N=10;
type
Any=integer;
var
A:array[0..N] of Any;
Left,Right,m,i,j:integer;
b:Any;
begin
writeln('Введите упорядоченную
последовательность эл-тов
массива ');
for i:=0 to N do readln(A[i]);
writeln('Введите ключ');
readln(b);
Left:=0;Right:=N;
while Left<Right do
begin
m:=(Left+Right) div 2;
if A[m]<b then Left:=m+1
else Right:=m;
end;
if (Right<>N) or ((Right=N) and (a[N]=b)) then
writeln('Эл-т
найден.
Позиция
эл-та: ',Right)
else
writeln('Элемента
нет');
end.
Нахождение элемента бинарным
поиском осуществляется очень
быстро. При поиске среди N
элементов требуется log2(N)
сравнений в наихудшем случае.
Кроме того, бинарный поиск уже при
N порядка 100 значительно
эффективнее
линейного - как по скорости
обнаружения, так и по способности
к
получению отрицательного
результата. Для доказательства
этого приведу следующие
характеристики линейного и
бинарного поиска:
1)
линейный поиск:
количество
элементов:10
среднее
количество сравнений при наличии
элемента:5
количество
сравнений при отсутствии
элемента:10
количество
элементов:1000
среднее
количество сравнений при наличии
элемента:500
количество
сравнений при отсутствии
элемента:1000
количество
элементов:1000000
среднее
количество сравнений при наличии
элемента:500000
количество
сравнений при отсутствии
элемента:1000000
1)
бинарный поиск:
количество
элементов:10
максимальное
количество сравнений при наличии
элемента:8
максимальное
количество сравнений при
отсутствии элемента:8
количество
элементов:1000
максимальное
количество сравнений при наличии
элемента:10
максимальное
количество сравнений при
отсутствии элемента:10
количество
элементов:1000000
максимальное
количество сравнений при наличии
элемента:20
максимальное
количество сравнений при
отсутствии элемента:20
Интерполяционный
поиск
Представим себе поиск слова в
словаре. Маловероятно, что мы
сначала заглянем в середину
словаря, затем отступим от начала
на 1/4 или 3/4 и т.д, как в бинарном
поиске.
Если нужное слово начинается с
буквы 'А', то и поиск имеет смысл
начинать в начале словаря. Когда
же найдена отправная точка для
поиска, дальнейшие действия будут
мало похожи на рассмотренные выше
методы.
Мы приходим к алгоритму,
называемому интерполяционным
поиском. Пусть задан массив
записей R1,R2,..Rk, снабженных
соответственно ключами K1,K2,..Kn.
Необходимо найти запись с данным
ключом K. Тогда, если известно, что
K лежит между Kl и Ku, то следующую
пробу делаем примерно на
расстоянии (u-l)*(K-Kl)/(Ku-Kl) от l,
предполагая, что ключи являются
числами, возрастающими
приблизительно как
арифметическая прогрессия.
Интерполяционный поиск требует в
среднем около log2 log2 N шагов, и
поэтому он предпочтительнее
бинарного при работе с большими
массивами.
Поиск
подстроки в строке.
Пусть
дана строка s и подстрока p. Тогда
для поиска подстроки p в строке s
возможно использование
следующего алгоритма:
var
s,p:string;
i,j,lp,ls:integer;
begin
{Ввод
строки и подстроки}
writeln('Введите строку');
readln(s);
ls:=length(s);
writeln('Введите подстроку');
readln(p);
lp:=length(p);
{Поиск
подстроки в строке}
i:=0;
repeat
i:=i+1;
j:=1;
while (j<lp) and (s[i+j]=p[j]) do
j:=j+1;
until (j=lp) or (i=lp-ls) or (i>ls);
if (j=lp) and (lp<>1) then writeln('Подстрока
в
строке
есть');
if i<>ls then writeln('Подстроки
в
строке
нет');
end.
Алгоритм
является эффективным, если
несовпадение символов строки и
подстроки происходит после
нескольких сравнений во
внутреннем цикле. Но, если
совпадение обнаружено в конце
строки, то требуется lp*ls сравнений.
Алгоритм
Кнута, Морриса и Пратта (КМП)
Этот алгоритм был создан в 1970 году
и получил свое название от имен
его разработчиков. Он состоит из
двух этапов: подготовительного и
основного.
На подготовительном этапе
учитывается структура подстроки.
Для этого формируется массив D, в
котором учитывается совпадения
символов подстроки с началом
подстроки следующим образом:
нулевой элемент массива D
получает значение равное -1. Далее
для каждой позиции j, совпадающей
с началом подстроки, вычисляется
максимальное количество
предшествующих ей символов. Если
же совпадений нет, то
соответствующий элемент массива D
равен -1. Размерность массива D
равна длине подстроки.
Теперь рассмотрим основной этап.
Поиск начинается со сравнения
первого символа строки с первым
символом подстроки. В случае
несовпадения происходит сдвиг
подстроки на количество символов,
указанных соответствующим
элементом массива D. Если
совпадения подстроки со строкой
не будет (то
есть данной подстроки в строке
нет), то программа выйдет из цикла
для поиска подстроки, когда i
будет равняться длине строки, то
есть если ни один символ
подстроки не совпадает ни с одним
символом строки, то программа
выполнит N сравнений, если же
совпадения отдельных элементов
подстроки(но не всей подстроки со
строкой) будут найдены, то в
наихудшем случае потребуется N+M
сравнений. Если же совпадение
подстроки со строкой обнаружится
сразу, то потребуется M cравнений.
uses
Crt;
const
Mmax=100;
Nmax=10000;
Esc=#27;
var
I, J, K, L, M, N : integer;
Ch : char;
P : array [0..Mmax-1] of char;
S : array [0..Nmax-1] of char;
D : array [0..Mmax-1] of integer;
begin
write('Введите строку');
N := 0; Ch := ReadKey;
While (Ch<>#13) and (N<Nmax-1) do
begin
write(Ch);
S[N] := Ch;
N:=N+1;
Ch
:= ReadKey
end;
writeln;
write('Введите
подстроку');
M := 0;
Ch := ReadKey;
While (Ch<>#13) and (M<Mmax-1) do
begin
write(Ch);
P[M] := Ch;
m:=m+1;
Ch := ReadKey;
end;
writeln;
write('Поиск
подстроки
: ');
if Ch=Esc then Exit;
J := 0; K := -1; D[0] := -1;
while J < M-1 do
begin
while (K >= 0) and (P[J]<>P[K]) do
K := D[K];
J:=J+1;
K:=K+1;
if P[J]=P[K] then D[J] := D[K]
else
D[J] := K;
end;
J := 0;
I := 0;
K := 0;
while (J<M) and (I<N) do
begin
while K<=I do
begin
Write(S[K]);
K:=K+1;
end;
while (J>=0) and (S[I]<>P[J]) do
J
:= D[J];
I:=I+1; J:=J+1;
end;
writeln;
if J = M then writeln('Образец
в
строке
присутствует')
else writeln('Образец в строке
отсутствует');
end.
|
