17-ma’ruza. Qidiruv va saralash

Misol

Berilgan a massivda x element nechanchi o`rinda joylashgan. Bunda a massiv elementlari soni n ta va qiymatlari o`sish bo`yicha tartiblangan.

Usul 1

uses crt;

type

mas = array[1..100] of integer;

var

n,i,x:integer;

a:mas;

function BinarySearch(a:mas;value,left,right:integer):integer;

var

middle:integer;

begin

if (left > right) then BinarySearch:= -1;

middle:= trunc((left+right)/2);

if (a[middle]=value) then

BinarySearch:=middle

else if(a[middle]>value) then

BinarySearch:=BinarySearch(a,value,left,middle-1)

else if (a[middle]

BinarySearch:=BinarySearch(a,value,middle+1,right)

end;

begin

readln(n,x);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

write(a[i],' ');

writeln('Berilgan ',x,' element massivda ',BinarySearch(a,x,1,n),' o`rinda joylashgan');

end.

Bu usul o`z navbatida ikkilik qidirish usuliga misol bo`la oladi ammo reqursivniy algaritm bo`lgani uchun katta o`lchamili massivlar bilan ishlaganda xotiradan yutkazadi.

Usul 2

uses crt;

type

mas = array[1..1000000] of integer;

var

n,i,x:integer;

a:mas;

function BinarySearch(a:mas;value,left,right:integer):integer;

var

middle:integer;

begin

while (true) do

begin

if (left > right) then

begin

BinarySearch:= -1;

break;

end;

middle:= trunc((left+right)/2);

if (a[middle]=value) then

begin

BinarySearch:=middle;

break;

end

else if(a[middle]>value) then

right:=middle - 1

else if (a[middle]

left:=middle+1;

end;

end;

begin

readln(n,x);

for i:=1 to n do

read(a[i]);

writeln('Berilgan ',x,' element massivda ',BinarySearch(a,x,1,n),' o`rinda joylashgan');

end.