Лекция: Алгоритмы поиска и их сравнение.

Осн-й вопрос задачи поиска: где в заданной совокупн. данных находится элемент, обладающий заданым св-вом. Большинство задач поиска сводится к простейшей – поиск в таблице эл-та с заданным значением.

Алгоритмы поиска. 1)Линейный поиск. Продолжает поиск до обнаружения искомого эл-та или до конца массива, последов-но перебирая все эл-ты; 2)Линейный поиск с использ-ем барьера. В массив на n+1 место записываем искомый эл-т X, который будет являться барьерным. Если эл-т будет найден только при i=n+1, значит, интересующего эл-та в массиве нет; 3)Бинарный поиск. Это один из методов непоследовательного поиска, назыв-ый также методом половинного деления. Идея: проверить, является ли x средним элементом массива. Если да, то ответ получен, если нет, то если x> среднего элемента то применить этот метод к левой половине массива, если x< среднего элемента, то применить этот метод к правой половине массива. Значение m=[(l+r)/2], где m – индекс среднего, l –первого, r – последнего элемента рассматриваемой части массива. Массив д.б. отсортирован При использ-и на каждом шаге область поиска сокращ-ся в 2 раза.;

begin

l:=1; r:=n; {на первом шаге рассмаривается весь массив}

f:=false;

while (l<=r)and not f do

begin

m:=(l+r)div2;

if a[m]=x then f:=true; {элемент найден. Поиск надо прекратить}

if a[m]<x then l:=m+1 {отбрасывается левая часть}

else r:=m-1; {отбрасывается правая часть}

end

end;

Анализ: Линейный поиск: число сравнений зависит от того, где располагается искомая запись. Если она окажется первой, выполняется только одно сравнение, если последней – n сравнений. Следовательно, успешный поиск требует в среднем (n+1)/2 сравнений. Неуспешный потребует n+1 сравнений с учетом барьерного эл-та. Бинарный поиск: каждое сравнение уменьшает число кандидатов в 2 раза, поиск применяется только в отсортированном массиве, тогда как последовательный поиск может работать в любом массиве. Поэтому, если необходимо произвести однократный поиск, лучше воспользоваться линейным поиском. 4)Поиск подстроки в строке. Прямой поиск. Сводится к послед-ым сравнениям отд-х символов. Поиск прод-ся до тех пор, пока не обнаруж-ся сравнение; 5)Поиск подстроки в строке. Алгоритм Бойера-Мура. Поиск ведется от начала строки, но с конца искомой подстроки, для которой форм-ся таблица, размерн-ть кот-й – 256. Эле-ми таблицы явл-ся расстояния от последнего символа искомой подстроки до ее каждого символа. Когда очередной символ подстроки не совпадает с очередным символов строки для последнего из таблицы расстояний опред-ся соответствующее расстояние, после чего конец искомой подстроки сдвиг-ся вправо на соответствующее число позиций, тем самым ряд позиций пропускается, сокращая время поиска. Всегда требуется меньше n сравнений, когда последний символ искомой строки x всегда попадает на несовпадающий символ строки s, число сравнений равно n/m, n – длина строки s, m – длина строки x; 6)Поиск подстроки в строке. Алгоритм Кнута-Мориса-Пратта. j – номер символа, входящего в образ, а d[j] – длина max последовательности символов образа x, предшествующих позиции j, которая совпадает полностью с началом образа.

Требует только n сравнений даже в самом плохом случае, где n – длина строки. Сравнение нач-ся с первого символа строки S.