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

Алгоритмы поиска информации

Пусть имеется некоторый набор данных и требуется определить, где в этом наборе находится заданный элемент (и есть ли он в наборе). Такая задача называется задачей поиска. Большинство задач поиска сводится к поиску в таблице (массиве) элемента с заданным значением.

Пример

Написать программу поиска элемента x в массиве из n элементов. Значение элемента x вводится с клавиатуры.

Решение

Пусть имеются следующие описания:

Const n = 10; { размерность массива }

Var a: array (1...n) Of Integer;

{ массив из n элементов целого типа }

x: Integer; { искомый элемент целого типа }

В данном случае известно только значение разыскиваемого элемента, никакой дополнительной информации о нем или о массиве, в котором его надо искать, нет. Проверка одного элемента не дает никакой информации об остальных. Поэтому для решения задачи разумно применить очевидный метод - последовательный просмотр массива и сравнение значения очередного рассматриваемого элемента с данным. Если значение очередного элемента совпадает с x, то запомним его номер в переменной к.

For i: =1 To n Do If a[i] = x Then k: = i;

Этот способ решения поставленной задачи, безусловно, приводит к цели, но обладает рядом существенных недостатков:

· если значение x встречается в массиве несколько раз, то найдено будет последнее из них;

· после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется n сравнений.

Разумно прекратить просмотр сразу после обнаружения заданного элемента. Так как в этом случае число повторений не известно, необходимо использовать цикл с предусловием. В результате:

- либо будет найден искомый элемент, то есть найдется такой индекс i, что а [ i ] = x;

- либо будет просмотрен весь массив, и искомый элемент не обнаружится.

Таким образом, поскольку нужно продолжать поиск до обнаружения искомого элемента или до конца массива, условие окончания цикла может выглядеть так:

While (i <= n) And (a[ i ]<> x) Do Inc (i);

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

Программа линейного поиска:

program n6;

const n=5;

var a:array[1..n] of integer;

{ массив из n элементов целого типа }

x:integer; { искомый элемент целого типа }

i,k:integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

writeln('Введите x');

readln(x);

for i:=1 to n do if a[i]=x then k:=i;

while (i<=n) and (a[i]<>x) do inc(i);

writeln('a[',k,']=',x,'=x');

end.

Дата добавления: 2014-11-09