Линейный поиск

Задача: поиск в массиве элемента с заданным значением. Последовательно просматриваем элементы массива и сравниваем их значения с искомым значением X.

Например.

For i:=1 To N Do If A[i]=X Then k:=i;

Находится номер (индекс) последнего элемента равного X (последнее вхождение), при этом массив просматривается полностью.

Первое вхождение ищем обратным циклом.

For i:=N DownTo 1 Do If A[i]=X Then k:=i;

Просто, но не эффективно! Возможно, вхождение уже найдено, а цикл просмотра продолжается до конца. Изменим программу.

{первое вхождение}

i:=1;

While (i<=N) And (A[i]<>X) Do Inc(i);{i:=i+1}

If i=N+1 Then Write('X нет в А')

Else Write('номер=', i);

Обратите внимание на заголовок цикла. Как только элемент будет найден, второе условие станет ложным и цикл завершится. При этом i будет равно или меньше N. Если нужный элемент не будет найден, то, в конце концов, станет ложным первое условие и цикл завершится при i большим N.

В программе предполагается, что если первое условие будет ложным, то второе условие не будет проверяться (уже ясно, что все сложное условие ложно). Поэтому условие (i<=N) стоит первым, в противном случае при i=N+1 возникает ошибка «нарушение границ массива» (при включенном контроле {$R+}). Вообще, при отладке (и только при отладке!) программы настоятельно рекомендуем включать такой контроль. При нарушениях границ массивов можно «испортить» значения других переменных, что сделает работу программы не предсказуемой.

Последнее вхождение будем искать аналогично.

i:=N;

While (i>0) And (A[i]<>X) Do Dec(i);{i:=i-1}

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i);

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

{не забудьте увеличить размер массива в описании}

{первое вхождение}

i:=1; A[N+1]:=X;

While A[i]<>X Do Inc(i);

If i=N+1 Then Then Write('X нет в А')

Else Write('номер=', i);

{последнее вхождение - первое с конца}

i:=N; A[0]:=X;

While A[i]<>X Do Dec(i);

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i);

Очевидно, что число сравнений зависит от места нахождения искомого элемента. В среднем количество сравнений равно (N+1) Div 2, в худшем случае - элемента нет в массиве, N сравнений