Sorting Data - Binary Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama.

Algoritma pencarian binary search 

 

Contoh penerapannya pada soal berikut 

Langkah pengerjaannya :

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.

Untuk lebih jelasnya, berikut video mengenai binary search :