Поиск элемента в упорядоченном массиве

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

Поиск ведется методом дихотомии.

Алгоритм:

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

2. Вводится искомая величина (m) и сравнивается со средним элементом. Если a[i]>m, то заданный элемент – в левой половине и поэтому индекс k правой границы устанавливается =i, иначе искомый элемент в правой половине и сдвигается начальный индекс p и p:=i.

3. Процесс повторяется пока (k-p)<=1, т.е. пока p и k не сдвинутся вплотную. При этом величина искомого индекса =p.

Примеры программ:

Задача. Из массива a составить массив b, который содержит только чётные элементы массива a.

program massiv1;

uses crt;

type mas=array[1..5] of integer;

var a,b:mas; i,k,nmin:integer; min:integer;

begin

clrscr;

textcolor (15);

for i:=1 to 5 do {Блок заполнения массива}

begin

writeln ('Введите значение элемента');

readln (a[i]);

end;

k:=0;

for i:=1 to 5 do if a[i] mod 2=0 then {Поиск чётного элемента}

begin k:=k+1; b[k]:=a[i]; end; {Формирование нового массива}

if k=0 then

begin textcolor (12); writeln ('Чётных элементов нет.'); writeln ('Формирование нового массива невозможно!');

end

else begin nmin:=1; min:=b[1]; {Поиск минимального в новом массиве}

for k:=1 to k do if b[k]<min then

begin min:=b[k]; nmin:=k; end;

for i:=1 to 5 do {Вывод элементов массива а}

begin textcolor (14); writeln ('Элемент ',i, ' массива a ',a[i]);

end;

for i:=1 to k do {Вывод элементов массива b}

begin

textcolor (9); writeln ('Элемент ',i, ' массива b ',b[i]);

end;

textcolor (10);

writeln ('Минимальный элемент среди чётных элементов массива=',min);

writeln ('Номер этого элемента=',nmin);

end;

repeat until keypressed; end.