Записки начинающего программиста часть 1. Turbo Pascal 7.0. Двоичный поиск в массиве.

Turbo Pascal. Записки начинающего программиста

Задача: допустим у нас есть векторный масив

0, 16, 16, 23, 25, 35, 40, 41, 42, 48, 53, 54, 60, 69, 77, 94

Нужно найти число 60

Нарисуем блок-схему

Блок-схема Procedure DblSearch(x,N,a,Posit)

Структура данных

Алгоритм поиска нужного значения (блок — схема)

Блок схема решения задачи двоичным методом на языке Pascal

Блок схема решения задачи двоичным методом на языке Pascal

Ну и листинг программы

uses crt;

const n=16;

type  mas=array [0..n-1] of integer;

procedure DblSearch(x,N:integer;a:mas;var Posit:integer);

var L,R,m:integer;

begin

L:=0; R:=N-1;

Posit:=-1;

while (L<=R)and(Posit<0) do

begin

m:=(L+R) div 2;

writeln(‘L=’,L,’ R=’,R,’ m=’,m,’ a[m]=’,a[m]);

if x>a[m] then L:=m+1 else

if x<a[m] then R:=m-1 else  Posit:=m;

end;

end;

var

AA:mas;

XX,i,Position:integer;

begin

clrscr;

AA[0] :=0;  AA[1] :=16;  AA[2]:= 16;  AA[3]:= 23; AA[4]:= 25;

AA[5] :=35; AA[6] :=40; AA[7]:= 41; AA[8]:= 42; AA[9]:= 48;

AA[10]:=53; AA[11]:=54; AA[12]:=60; AA[13]:=69; AA[14]:=77; AA[15]:=94;

writeln(‘Масив:’);

for i:=0 to n-1 do write(AA[i]:4);

writeln;

repeat

begin

writeln;

writeln(‘Ввести целое число <>0 для поиска, или 0 для завершення работы’);

read(XX);

DblSearch(XX,n,AA,Position);

if Position>=0 then writeln(‘Число ‘,AA[Position],’ найдено под индексом ‘

,Position,’;  ( Диапазон индекса = 0-’,n-1,’)')

else writeln(‘Число ‘,XX,’ не найдено’);

end until XX=0;

end.

Результат выполнения работы программы  ("Двоичный поиск значения в массиве данных")

Для тестирования можете скачать листинг программы и протестировать.

Turbo Pascal можно скачать здесь