Поиск в массиве

Поиск в массиве

1.      Метод перебора:

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

……..

I:= 0;

NAIDEN:= FALSE; REPEAT

I:= I+1;

IF A[I] = ISKOMOE THEN

NAIDEN:=TRUE; UNTIL NAIDEN OR (I=N); IF NAIDEN

THEN

WRITELN(‘Элемент найден, его номер - ‘,I) ELSE

WRITELN(‘Элемент не найден’);

…………

2.      Метод бинарного поиска:

Метод бинарного поиска (метод деления пополам) используется только для упорядоченных массивов. Суть его заключается в том, что находится центральный (серединный) элемент массива и сравнивается с искомым. Если они равны, то поиск прекращается. Если они не равны, то, если искомый элемент больше центрального (при сортировке по возрастанию), из рассмотрения исключается половина массива от первого до центрального элемента включительно. Если же искомый элемент меньше центрального, то исключается часть массива, начиная от центрального до последнего элемента. В остальной части находится центральный элемент и сравнивается с искомым и т.д. до тех пор, как произойдёт совпадение или начало области поиска станет больше её конца.

………

NAIDEN:= FALSE;

NA:= 1;      // номер первого элемента области поиска KO:= N;                   // номер последнего элемента области поиска REPEAT

SR:=(KO-NA) DIV 2+NA; IF A[SR] = ISKOMOE

THEN

NAIDEN:=TRUE ELSE

IF ISKOMOE > A[SR] THEN

NA:= SR+1 ELSE

KO:= SR-1; UNTIL NAIDEN OR (NA>KO); IF NAIDEN

THEN

WRITELN(‘Элемент найден, его номер - ‘,SR) ELSE

WRITELN(‘Элемент не найден’);