Двоичный поиск (или бинарный, или поиск делением пополам)

Принцип метода:

Алгоритм двоичного поиска допустимо использовать для нахождения заданного элемента ТОЛЬКО В УПОРЯДОЧЕННЫХ МАССИВАХ. Допустим имеем массив упорядоченный по не убыванию (Vector[i]<=Vector[i+1]).

Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается. Если же средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. Следовательно их можно исключить из зоны дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остается левая.

На втором этапе выполняются аналогичные действия с оставшейся половиной массива. В результате второго этапа остается ¼ часть массива. И т.д., пока или искомый элемент будет найден, или длина зоны поиска станет равной нулю (т.е. искомый элемент не найден – отсутствует в массиве).

Program BinSearch;

uses Crt;

const n=20; {Длина массива}

type

TVector=array[1..n] of Real;

TStudentCard = record

SurName : String20; {Фамилия}

Name : String20; {Имя}

FatherName : String20; {Отчество}

Year : Integer; {Год рождения}

HomeAddress: String; {Домашний адрес}

GroupCode : String7; {Шифр группы}

Marks : Tmarks; {Оценки за последний семестр}

end;

Tgroup = array[1..20] of TStudentCard;

var

Vector:TVector; {исходный массив}

X :Real;

L,R :Integer; {Границы зоны поиска}

i :Integer;

GroupRPZ_10_02,

GroupRPZ_09_01 : Tgroup;

begin

ClrScr;

GroupRPZ_10_02[1].SurName := 'Vakulanko';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 5;

GroupRPZ_10_02[1].SurName := 'Danchenko';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 3;

GroupRPZ_10_02[1].SurName := 'Kuznesov';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 4;

Writeln('Введите элементы массива');

for i:=1 to n do Read(Vector[i]); Readln;

Write('Введите искомый элемент');

Readln(X);

{---------------------------------------------}

L:=1; R:=n;

While (L<=R) do {Пока не пересекутся границы}

begin

i:=(L+R)div2; {Индекс среднего элемента}

if Vector[i]<X then

Break {элемент найде - выход из цикла}

else

if Vector[i]<X then L:=i+1

else R:=i-1;

end; {while}

if Vector[i]=X then

Writeln('Искомый элемент найден на позиции ',i:3);

else

Writeln('Искомый элемент не найден');

end.

ВАРИАНТ №5

Работа с двумерными массивами (матрицами)

Задача. Дан двумерный массив (матрица) размерностиm*n, элементами которого являются целые числа. Выполнить зеркальное отображение элементов матрицы относительно вертикальной оси симметрии (поменять местами элементы первого столбца с последним, второго с предпоследним и т.д.).

Program VertMirrow;

uses Crt;

const

m=10; {число строк}

n=15; {число столбцов}

type

Tmatr=array[1..m,1..n] of Integer;

TStudentCard = record

SurName : String20; {Фамилия}

Name : String20; {Имя}

FatherName : String20; {Отчество}

Year : Integer; {Год рождения}

HomeAddress: String; {Домашний адрес}

GroupCode : String7; {Шифр группы}

Marks : Tmarks; {Оценки за последний семестр}

end;

Tgroup = array[1..20] of TStudentCard;

var

Matr:TMatr; {исходная матрица}

Finp:Text; {файл исходных данных}

B,i,j:Integer;

GroupRPZ_10_02,

GroupRPZ_09_01 : Tgroup;

procedure PrintMatr;

begin

for i:=1 to m do

begin

for j:=1 to n do Write(Matr[i,j]:5);

Writeln;

end;

Writeln;

end; {PrintMatr}

begin

ClrScr;

GroupRPZ_10_02[1].SurName := 'Vakulanko';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 5;

GroupRPZ_10_02[1].SurName := 'Danchenko';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 3;

GroupRPZ_10_02[1].SurName := 'Kuznesov';

GroupRPZ_10_02[1].Marks.Prog := 3;

GroupRPZ_10_02[1].Marks.Philosofy := 4;

{чтение исходных значений матрицы из файла}

Assign(Finp,'Finp.dat');

Reset(Finp);

for i:=1 to m do

begin

for j:=1 to n do Read(Finp, Matr[i,j]);

Readln(Finp);

end;

Writeln('Исходная матрица');

PrintMatr;

{Зеркальное отображение матрицы относительно вертикальной оси}

for j:=1 to n div 2 do

{Берем столбцы от первого до среднего}

fori:=1tomdo

{Меняем местами симметричные столбцы}

begin

B:=Matr[i,j];

Matr[j,i]:=Matr[i,n-j+1];

Matr[i,n-j+1]:=B;

end;

Writeln('Преобразованная матрица');

PrintMatr;

end.

ВАРИАНТ №6