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-
j←n ,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 Comments