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 <>and (not ketemu) do

Tengah ¬ (BatasAtas + BatasBawah) div 2

If A [Tengah] = cari then

Ketemu ¬ true

Else

If ( A [Tengah] <>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," 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," 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.

referensi :
http://mita.staff.gunadarma.ac.id/Downloads/files/14270/BINARY-SEARCH.doc