0 Tugas V ANALISIS DAN PERANCANGAN ALGORITMA

Share

1.Flochart

2. Pseudocode
procedure PencarianBiner(input a1, a2, ..., an : integer, x : integer, output idx : integer)
Deklarasi
i, j, mid : integer
ketemu : boolean
Algoritma
i←1
j←n
ketemu←false
while (not ketemu) and ( i ≤ j) do
mid ← (i+j) div 2
if amid = x then
ketemu ← true
else
if amid < x then { cari di belahan kanan }
i←mid + 1
else { cari di belahan kiri }
j←mid - 1;
endif
endif
endwhile
{ketemu or i > j }
if ketemu then
idx←mid
else
idx←0
endif

3. Program:

Program PencarianBinarySearch;
uses crt;
Type
Arr = Array[1..10000] of Integer;
Var
A : Arr ;
i,j : Integer ;
N1, X1, IX1 :Integer ;
Procedure CariBinarySearch(L : Arr ; N : Integer; Var IX : Integer);
Var
Ia, Ib :Integer;
K : Integer;
ketemu : Boolean;
Begin
Ia := 1;
Ib := N;
ketemu :=false;
while (not ketemu) and (Ia<=Ib) do
Begin
k:=(Ia+Ib)div 2;
if (L [k]=IX)then
ketemu :=true
else
if (L [k] < IX) then
Ia :=k+1
else
Ib :=k-1;
End;
if (ketemu) then
writeln('ketemu di index ke :',k)
else
writeln('tidak ketemu');
End;
begin
Clrscr;
write( 'Berapa Data yang dimasukkan : ');Readln(N1);
for i := 1 to N1 do
Begin
write('Data ke-', i , ' : ');Readln(A [i]);
end;
write ('Masukkan Data yang dicari : ');Readln(IX1);
CariBinarySearch (A, N1, IX1);
Readln;
End.


4. Kompleksitas waktu


a) Kasus terbaik
Tmin(n) = 1

b) Kasus terburuk:
Tmax (n) = 2log n

Read more