ALGORITMA PENCARIAN BINER (BINARY SEARCH)
ALGORITMA PENCARIAN BINER (BINARY SEARCH)
Pencarian Biner (Binary Search) pada array yang sudah
terurut
Pencarian Biner (Binary Search) dilakukan
untuk :
♪ memperkecil jumlah
operasi pembandingan yang harus dilakukan antara data yang dicari dengan data
yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar
ukurannya.
♪ Prinsip dasarnya
adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai
data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada
kemungkinan data tidak ditemukan).
♪ Syarat utama untuk
pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan
terurut menaik.
ALGORITMA
Kamus
Const N : integer = 8
{ misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas ¬ 1 { indeks array dimulai dari 1
}
BatasBawah ¬ N
Ketemu ¬ False
While (BatasAtas < BatasBawah) and (not
ketemu) do
Tengah ¬ (BatasAtas
+ BatasBawah) div 2
If A [Tengah] = cari then
Ketemu ¬ true
Else
If ( A
[Tengah] < cari ) then { cari
di bagian kanan }
BatasAtas
¬ Tengah + 1
Else
BatasBawah ¬ Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output
( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif
Contoh Nilai-Nilai data yang sudah
terurut :
|
A
|
2
|
5
|
8
|
12
|
15
|
25
|
37
|
57
|
|
|
1
|
2
|
3
|
3
|
5
|
6
|
7
|
8
|
Kasus 1 : cari = 12
Loop
pertama : Tengah
= (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] =
12, berarti loop pertama data langsung ditemukan
Kasus 2 : cari = 15
Loop
pertama : Tengah
= (BatasAtas + BatasBawah) div 2 = (1 +
8) div 2 = 4
A
[Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 =
5
Loop
kedua : Tengah
= (BatasAtas + BatasBawah) div 2 = (5 +
8) div 2 = 6
A
[Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 =
5
Loop
ketiga : Tengah
= (BatasAtas + BatasBawah) div 2 = (5 +
5) div 2 = 5
A
[Tengah] = A [5] = 15, berarti setelah
loop ketiga, data ditemukan
Kasus 3 : cari = 10
Loop
pertama : Tengah
= (BatasAtas + BatasBawah) div 2 = (1 +
8) div 2 = 4
A
[Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 =
3
Loop
kedua : Tengah
= (BatasAtas + BatasBawah) div 2 = (1 +
3) div 2 = 2
A
[Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop
ketiga : Tengah
= (BatasAtas + BatasBawah) div 2 = (3 +
3) div 2 = 3
A
[Tengah] = A [3] = 8, berarti setelah
loop ketiga, data tidak ditemukan
Untuk jumlah
data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n )
kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal
sebanyak 3 kali.
0 komentar:
Post a Comment