Если нет никакой дополнительной информации об имеющемся наборе данных, остается лишь полный перебор всех ключей. При этом, если в наборе N значений, среднее число просматриваемых ключей равно N/2. Это легко объяснить: искомый ключ может оказаться и первым (один просмотр), и последним (N просмотров), а в среднем и получится N/2. Алгоритм линейного поиска очень простой:
CONST N=100;
TYPE TA=ARRAY[1..N] OF WORD;
VAR a:TA; x: WORD; I:BYTE;
BEGIN
…
i:=0;
WHILE (I<N) AND (a[I]<>x) DO
INC(I);
Казалось бы, тут "ни прибавить, ни убавить". Однако есть средство сделать такой алгоритм существенно более быстрым. Обратите внимание, что в заголовке цикла WHILE проверяются два условия: совпадение ключей и выход за границы массива. Можно сделать следующее: добавить к концу массива еще один элемент и перед поиском занести в него искомое значение ключа. Тогда в цикле останется проверять только условие совпадения с ключом, поскольку ключ в массиве гарантированное есть – или "настоящий" который мы и ищем, или "подставной", добавленный в конец. Программа выглядит следующим образом:
CONST N=100;
TYPE TA=ARRAY[1..N+1] OF WORD;
VAR a:TA; x: WORD; I:BYTE;
BEGIN
…
a[N+1] := x; { искомое значение }
i := 0;
WHILE (a[I]<>x) DO
INC(I);
