Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами. Строковый тип определяется так:
String = array[0..М 1] of char
соответственно определяется и отношение порядка для строк x и y:
x = y, если xj = yj для 0 face="Symbol" =< j < M
x < y, если xi < yi для 0 face="Symbol" =< i < M и xj = yj для 0 face="Symbol" =< j < i
Для того чтобы установить факт совпадения, необходимо установить, что все символы сравниваемых строк соответственно равны один другому. Поэтому сравнение составных операндов сводится к поиску их несовпадающих частей, т. е. к поиску ⌠на неравенство■. Если неравных частей не существует, то можно говорить о равенстве. Предположим, что размер слов достаточно мал, скажем, меньше 30. В этом случае можно использовать линейный поиск и поступать таким образом.
Для большинства практических приложений желательно исходить из того, что строки имеют переменный размер. Это предполагает, что размер указывается в каждой отдельной строке. Если исходить из ранее описанного типа, то размер не должен превосходить максимального размера M. Такая схема достаточно гибка и подходит для многих случаев, в то же время она позволяет избежать сложностей динамического распределения памяти. Чаще всего используются два таких представления размера строк:
Размер неявно указывается путем добавления концевого символа, больше этот символ нигде не употребляется. Обычно для этой цели используется ⌠непечатаемый■ символ со значением 00h. (Для дальнейшего важно, что это минимальный символ из всего множества символов.)
Размер явно хранится в качестве первого элемента массива, т. е. строка s имеет следующий вид: s = s0, s1, s2, ..., sM-1. Здесь s1, ..., sM-1 фактические символы строки, а s0 = Chr(M). Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен размером множества символов (256).
В последующем алгоритме поиска отдается предпочтение первой схеме. В этом случае сравнение строк выполняется так:
i:=0;
while (x[i]=y[i]) and (x[i]<>00h) do i:=i+1
Концевой символ работает здесь как барьер.
Теперь вернемся к задаче поиска в таблице. Он требует ⌠вложенных■ поисков, а именно: поиска по строчкам таблицы, а для каждой строчки последовательных сравнений между компонентами. Например, пусть таблица T и аргумент поиска x определяются таким образом:
T: array[0..N-1] of String;
x: String
Допустим, N достаточно велико, а таблица упорядочена в алфавитном порядке. При использовании алгоритма поиска делением пополам и алгоритма сравнения строк, речь о которых шла выше, получаем такой фрагмент программы:
L:=0; R:=N;
while L<R do begin
m:=(L+R) div 2; i:=0;
while (T[m,i]=x[i]) and (x[i]<>00h) do i:=i+1;
if T[m,i]<x[i] then L:=m+1 else R:=m
end;
if R<N then begin
i:=0;
while (T[R,i]=х[i]) and (х[i]<>00h) do i:=i+1
end
{(R<N) and (T[R,i]=x[i]) фиксирует совпадение}
Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки. Его можно определить следующим образом. Пусть задан массив s из N элементов и массив p из M элементов, причем 0 < M face="Symbol" =< N. Описаны они так:
s: array[0..N 1] of Item
р: array[0..M 1] of Item
Поиск строки обнаруживает первое вхождение p в s. Обычно Item это символы, т.е. s можно считать некоторым текстом, а p словом, и необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов, отсюда и очевидная заинтересованность в поиске эффективного алгоритма для этой задачи. Разберем алгоритм поиска, который будем называть прямым поиском строки.
Алгоритм 3.
i:=-1;
repeat
i:=i+1; j:=0;
while (j<M) and (s[i+j]=p[j]) do j:=j+1;
until (j=M) or (i=N-M)
Вложенный цикл с предусловием начинает выполняться тогда, когда первый символ слова p совпадает с очередным, i-м, символом текста s. Этот цикл повторяется столько раз, сколько совпадает символов текста s, начиная с i-го символа, с символами слова p (максимальное количество повторений равно M). Цикл завершается при исчерпании символов слова p (перестает выполняться условие j<M) или при несовпадении очередных символов s и p (перестает выполняться условие s[i+j]=p[j]). Количество совпадений подсчитывается с использованием j. Если совпадение произошло со всеми символами слова p (т.е. слово p найдено), то выполняется условие j=M, и алгоритм завершается. В противном случае поиск продолжается до тех пор, пока не просмотренной останется часть текста s, которая содержит символов, меньше, чем есть в слове p (т.е. этот остаток уже не может совпасть со словом p). В этом случае выполняется условие i=N-M, что тоже приводит к завершению алгоритма. Это показывает гарантированность окончания алгоритма.
Этот алгоритм работает достаточно эффективно, если допустить, что несовпадение пары символов происходит после незначительного количества сравнений во внутреннем цикле. При большой мощности типа Item это достаточно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае производительность будет внушать опасение.
