Метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.
Одним из эффективных методов поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента.
program Find_Bin;
const
Count =20;
M : array[1..Count] of byte =
(20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1)
var
N, I, First, Last : Byte;
A : integer;
Found : boolean ;
begin
Writeln('Исходный массив:');
for I := 1 to Count do Write (M[I] :3,' '); Writeln; Writeln;
Write('Введите значение элемента массива для поиска >');
Readln(N);
А:=0;
First := 1;
Last := Count;
Found:=False; {Элемент не найден}
repeat {Повторять поиск}
I := (First + Last) div 2; {Разделить на две части}
if M[I] = N then Found:=True
else
begin
if M[I] > N then First := I+1 {Искать элемент в правой части}
else Last := I—1; {Искать элемент в левой части}
end;
А:=А+1; {Увеличить счетчик числа итераций}
until (Found) or (First>Last); {Завершить, если найдется искомый элемент или будет просмотрен весь массив}
if Found then Writeln('Искомый элемент ',N,' в массиве занимает ',I,'-ю позицию')
else
Writeln('В массиве нет искомого элемента ',N);
Writeln('Поиск выполнен За ',А,' итераций');
end.
|