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
|
