Поисковые задачи для массивов

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

- линейный поиск;

поиск с барьером;

дихотомический поиск.

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

Алгоритмом такого поиска был рассмотрен при решении типовых задач на построение циклических алгоритмов. Напомним, что особенностью такого поиска является две причины прекращения поиска:

Элемент найден (это программируется с помощью логической переменной)

Просмотрены все элементы, но заданный элемент так и не нашли

(i > n)

const n = 20; {количество элементов в массиве}

var a: array [1..n] of integer; {исходный массив}

i, x: integer;

f: boolean;

begin

write (‘задайте искомый элемент’);

readln (x);

writeln (‘задайте элементы массива’);

for i: = 1 to n do

readln (a[i]);

f: = false; {элемент ещё не найден}

i: = 1;

while (i < = n) and not f do

if a[i] = x then f: = true {нашли}

else i: = i + 1 {переходим к следующему элементу}

if f then writeln (‘ нашли элемент с номером‘, i)

else writeln (‘такого элемента нет’)

End.

Поиск с барьером

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

сonst n = 20; {количество элементов в массиве}

var a: array [1..n + 1] of integer; {исходный массив}

i, x: integer;

begin

write (‘задайте искомый элемент’);

readln (x);

writeln (‘задайте элементы массива’);

for i: = 1 to n do

readln (a[i]);

a[n + 1]: = x; {установлен барьер, равный х, в конце}

i: = 1; {массива}

while a[i] <> x do

i: = i + 1; {переходим к следующему элементу}

if i <> n + 1 then writeln (‘нашли элемент с номером’, i)

else writeln (‘такого элемента нет’):

End.