Binary Search

Binary Search merupakan sebuah teknik pencarian data dengancara berulang kali membagi separuh dari jumlah data yang dicari sampai sehingga memperkecil lokasi pencarian menjadi satu data. Dengan teknik ini kita akanmembuang setengah dari jumlah data. Apabila ditemukan kecocokan data maka program akan mengembalikan output, jika tidak pencarian akan terus berlanjut hingga akhir dari pembagian jumlah data tersebut. Algotihma ini biasanya banyak digunakan untuk mencari di program dengan jumlah data yang banyak, dimana kompleksitas dari algorithma ini adalah Ο(log n) di mana n adalah jumlah item. Pada saat menggunakan binary search, data yang berada di dalam array harus diurutkan terlebih dahulu.

Misalkan kita memiliki int arr[] = {70, 60, 30, 50, 40,20}, data para int arr harus diurutkan terlebih dahulu menggunakan teknik sorting seperti bubble sort. Sehingga array kita akan menjadi int arr[] = {20,30,40,50,60,70}. Apabila angka yang dicari adalah angka 40, berikut gambaran dari implementasi BinarySearch:

1st Cycle:
(20,30,40,50,60,70)
LOW = 0
HIGH = N
MID = (LOW + HIGH)/2 = (0+6)/2 = 3
(arr[MID] == 40)
(20,30,40,50,60,70)
(50==40) // FALSE
HIGH = MID-1

*Array di mulai dari index ke 0, maka index ke 3 berisi nilai 50. 

2nd Cycle:
(20,30,40,50,60,70)
MID = (LOW + HIGH)/2 = (0+2)/2 = 1
(arr[MID] == 40)
(20,30,40,50,60,70)
(30==40) // FALSE
LOW = MID+1

3rd Cycle:
(20,30,40,50,60,70)
MID = (LOW + HIGH)/2 = (2+2)/2=2
(arr[MID] == 40)
(20,30,40,50,60,70)
(40==40) // TRUE

Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.

Berikut implementasi dari Binary Search menggunakan Bahasa C:

Reference:

Paul Deitel & Harvey Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson  Education. Hoboken. ISBN: 9780133976892.