1.3. Поиск в таблице
 

Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами.

Строковый тип определяется следующим образом:
char A[M];
Соответственно определяется и отношение порядка для строк:
(x=y)=(A_j: 0≤j<M: x_j=y_j),
(x<y)=E_i: 0≤i<N: ((A_j: 0≤y<i: x_j=y_j)&(x_i<y_i)).

Для того чтобы установить факт совпадения, мы должны, очевидно, убедиться, что все символы сравниваемых строк соответственно равны один другому. Поэтому сравнение составных операндов сводится к поиску их несовпадающих частей, т. е. к поиску "на неравенство". Если неравных частей не существует, можно говорить о равенстве. Предположим, что размер слов достаточно мал, скажем меньше 30. В этом случае мы будем использовать линейный поиск и поступать таким образом.

Для большинства практических приложений желательно исходить из того, что строки имеют переменный размер. Это предполагает, что размер указывается в каждой отдельной строке. Если исходить из ранее описанного типа, то размер не должен превосходить максимального размера М. Такая схема достаточно гибка и подходит для многих случаев, в то же время она позволяет избежать сложностей динамического распределения памяти. Чаще всего используются два представле-ния размера строк:

1. Размер неявно указывается путем добавления концевого символа, и больше этот символ нигде не употребляется. Обычно для этой цели используется "непечатаемый" символ со значением «0». (И для дальнейшего это очень важно, что это минималъный символ из всего множества символов.)
2. Размер явно хранится в качестве первого элемента массива, т. е. строка s имеет следующий вид: s = S₀, S₁, S₂,…, S_n-1. Здесь S₁, S₂,…,S_n-1 — фактические символы строки, a s₀ – количество символов. Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен размером множества символов (256).

С учётом первой схемы алгоритм сравнение строк выполняется так:

Концевой символ работает как барьер,а инвариант цикла таков:
Aj: 0≤j<i: x_j=y_j!=0x00

Результирующее же условие выглядит следующим образом:
((x_i!=y_i)OR(x_i=0x00))&(A_j: 0≤j <i$ x_j=y_j!=0x00).

При условии x_i=y_i считается, что х и у совпадают, если же x_i<y_i то x<y.

Теперь мы готовы вернуться к задаче поиска в таблице. Он требует "вложенных" поисков, а именно: поиска по строчкам таблицы, а для каждой строчки последовательных сравнений — между компонентами. Например, пусть таблица Т и аргумент поиска х определяются таким образом:
char T[N-1], x;

Допустим, N достаточно велико, а таблица упорядочена в алфавитном порядке. Воспользуемся поиском делением пополам. Используя соответствующие алгоритмы и сравнения строк , о которых шла речь выше, получаем такой фрагмент программы:
L=0; R=N;
while (L<N) {
m=(L+R)/2;
i=0;
while ((T[m,i]=x[i])&&(x[i]!=0x00) i++;
if (T[m,i]<x[i]) L=m+1;
else R=m;
}
if (Rwhile ((T[R,i]=x[i])&&(x[i]!=0x00) i++;
/* (R<N) & (T[R,i]=x[i]) фиксирует совпадение */