Binary Searching

Binary search merupakan salah satu metode searching, binary search hanya bisa dilakukan pada data yg telah tersort ato terurut karena proses algoritmanya yg terus menerus membagi data menjadi 2 bagian hingga angka / input yg dicari ditemukan. Selection Sorting adalah teknik atau cara untuk mengurutkan suatu deretan data.

Berikut adalah pencarian Biner (Binary Search) pada array yang sudah terurut:

♪ 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.

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," batasatas =" Tengah" 1 =" 4" 1 =" 5" tengah =" (BatasAtas" 2 =" (5" 2 =" 6"> 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" tengah =" (BatasAtas" 2 =" (3" 2 =" 3" style="font-weight: bold;">

Kasus :

Temukan bilangan 9 pada deret 3, 5, 7, 8, 9, 12, 15 ?

Jawaban:

Array awal





Temukan nilai tengah





Abaikan Subarray yang kurang dari 8





Temukan nilai tengah





Abaikan subarray yang lebih dari 12





Karena elemen tinggal satu, maka elemen tersebut adalah elemen yang dicari





Referensi:

http://www.stttelkom.ac.id/staf/zka/Algoritma%20Divide%20and%20Conquer.pdf

http://www.informatika.org/~rinaldi/Stmik/Algoritma%20Divide%20and%20Conquer%20(lanjutan).ppt

http://www.informatika.org/~rinaldi/Stmik/Algoritma%20Divide%20and%20Conquer.ppt