A.         Algoritma pencarian Beruntun ( Pencarian lurus)


Algiritma pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun,mulai dari elemen pertama ,sampai elemen yang dicari sudah ditemukan atau seluruh elemen sudah diperiksa.


Langkah-langkah algoritma pencarian beruntun


Contoh :
Terdapat larik L dengan 6 indeks :


7
9
3
12
10
6

Misalkan nilai yang dicari adalah x=10
Elemen yang dibandingkan (berturut-turut) : 7,9,3,12,10 (ditemukan) Jadi x = 10 ditemukan pada indeks =5


Misalkan nilai yang dicari adalah x=13
Elemen yang dibandingkan (berturut-turut) : 7,9,3,12,10,6 (tidak ditemukan) Jadi x = 13 tidak ada dalam larik L indeks = -1


Contoh algoritma pencarian beruntun : Deklarasi:
I : integer; {pencatat indeks larik}
Algoritma:
I 1
While (I < n) and (L*i+ x) do
I I +1
Endwhile
{ i=n or L[i]= x}
If L[i] = x then {x ditemukan }
ketemu true

else

endif

ketemu false , x tidak ditemukan -




B.   Algoritma Pencarian Bagi Dua


Algoritma ini digunakan untuk mencari arti kata tertentu di dalam kamus,kita tidak membuka kamus itu dari halaman awal sampai halaman akhir satu per satu,namun kita mencarinya dengan cara membelah atau membagi dua buku itu,jika kata yang dicari tidak ditemukan pada pertengahan itu,kita cari lagi dibelahan bagian kiri atau kanan dengan cara

membagi dua belahan yang dimaksut,begitu seterusnya sampai ketemu.Dan kamus ini sudah terurut.


Misalkan indeks kiri adalah I dan indeks kanan adalah j.awalnya kita misalkan i = 1 dan j dengan n.
Langkah 1            : bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan  indeks k=(i+j) div 2.(L[k],membagi larik menjadi 2 bagian,yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j])
Langkah 2             : Periksa apakah L[k] = x. jika L[k]=x maka pencarian selesai,tapi jika salah maka harus ditentukan apakah pencarian dilanjutkan di larik kiri atau kanan.
Langkah 3             :ulangio langkah satu hingga x ditemukanatau i>j atau ukuran larik sudah nol. Contoh : carilah x= 31 pada larik L dengan 8 indeks

99
51
40
31
22
18
15
3
i=1          2        3         4           5         6           7        8=j


Langkah 1             : i=1 dan j=8
L [k] = (1+8) div 2=4(elemen yang diarsia)


99
51
40
31
22
18
15
3
1              2        3         4           5         6           7        8
Langkah2              : pembandingan: L[4]=31 ya!(ditemukan,proses pencarian selesai) Misalkan elemen yang dicari adalagh x=22
Langkah 1             : i=1 dan j=8
L[k]=(1+8) div 2= 4 (elemen yang di arsir)


99
51
40
31
22
18
15
3
1              2        3         4           5         6           7        8
Langkah 2             : pembandingan L[4]= 22?tidak,harus diputuskan apakah pencarian dilakukan dibagian kiri atau kanan.
Pembandingan L[k]>22?ya,lakukan pencarian pada larik bagian kanan dengan i
= k+1=5 dan j=8

22
18
15
3
I=5          6               7               j=8
Langkah 3             : i=5 dan j=8
L[k]= (5+8) div 2= 6(elemen yang diarsir)

22
18
15
3
5              6               7               8

Langkah 4             : pembandingan L[6]=22?tidak,harus diputuskan apakah pencarian dilakukan dibagian kiri atau kanan.
Pembandingan L[6] >22?tidak,lakukan pencarian pada larik bagian kiri dengan
i=5 dan j= k-1=5
22
5
Langkah 5             : i=5 dan j=5
L[k]= (5+5) div 2 = 5(elemen yang diarsir)
22
5
Langkah 6             : L[5] = 22?ya, x ditemukan proses pencarian selesai
Contoh algoritma pencarian bagi dua : Deklarasi :
I, j, k : integer;
Ketemu : Boolean ; Algoritma:
i 1 ,ujung kiri larik-
jn ,ujung kanan larik-
ketemu false ,dimisalkan x belum ditemukan-
while (not ketemu) and (I <= j) do
k (i+j) div 2 ,bagi dua larik L pada posisi k-
if (L[k] = x) then ketemu true else ,L*k+ x-
if ( L[k] > x) then
{lakukan pencarian pada larik bagian kanan,set indeks ujung kiri larik yang baru}
i k+1
else
{lakukan pencarian pada larik bagian kiri,set indeks ujung kanan larik yang beru}
J k-1
Endif
Endif
Endwhile
{ketemu=true or i>j}
If ketemu then  {x ditemukan}
idx k
else {x tidak ditemukan di dalam larik}
idx-1
endif

0 komentar:

 
Easyonlineplace © 2013. All Rights Reserved. Powered by Blogger
Top