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.

Algoritmanya :

Contoh Nilai-Nilai data yang sudah terurut :

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.

Sumber :

http://andikafisma.wordpress.com/algoritma-pencarian-biner-binary-search/