Dhiekalantana's blog

Binary search merupakan salah satu algoritma untuk melalukan pencarian pada array yang sudah terurut. Jika kita tidak mengetahui informasi bagaimana integer dalam array, maka penggunaan binary search akan menjadi tidak efisien, kita harus melakukan sorting terlebih dahulu atau menggunakan metode lain yaitu linear search. Namun jika kita telah mengetahui integer dalam array terorganisasi baik secara menaik atau menurun, maka bisa dengan cepat menggunakan algoritma binary search. Adapun ide dasar binary search yaitu memulai pencarian dengan membagi dua ruang pencarian. Misalnya kita memiliki array A, dan kita ingin menemukan lokasi dari spesifik target integer K dalam array. Ada 3 kemungkinan kondisi pada binary search yaitu:

1. Jika data target K langsung di temukan, maka proses pembagian ruangan berhenti. Kemudian print out indeks data elemen pada array.
2. Jika data target K < A[middle], maka pencarian dapat dibatasi hanya dengan melakukan pencarian pada sisi kiri array dari A[middle]. Seluruh elemen yang berada di sebelah kanan dapat di abaikan.
3. Jika data target K > A[middle], maka akan lebih cepat jika pencarian di batasi hanya pada bagian sebelah kanan saja.
4. Jika seluruh data telah di cari namun tidak ada, maka diberi nilai seperti -1

Sekarang mari kita analisis metode binary search untuk menentukan kompleksitasnya. Ketika jumlah elemen dalam array 8:

Ketika n=8, Binary Search dijalankan dengan mereduksi ukuran menjadi 4

Ketika n=4, Binary Search dijalankan dengan mereduksi ukuran menjadi 2

Ketika n=2, Binary Search dijalankan dengan mereduksi ukuran menjadi 1

Dapat kita lihat bahwa binary search dipanggil sebanyak tiga kali (3 elemen dalam array yang dieksekusi) untuk n = 8.

Sehingga didapat 8 = 2³ atau secara general kita katakan n = 2^k. ketika kita mengeksekusi x   pencarian, “while loop” juga dieksekusi sebanyak x kali dan n di reduksi ukurannya menjadi 1. Pada contoh penerapan di atas, dapat disimpulkan jumlah maksimum total operasi yang dilakukan adalah sebanyak 3. Nilai dari k dapat dinotasikan menjadi

2^k = n sehingga k = log₂ n

Jumlah operasi yang dilakukan untuk mencari k adalah sebanyak = 3 log n. pada kasus terburuk, yaitu kasus dimana k tidak terdapat dalam array adalah

T(n) = log₂ n

Misalnya jika kita memiliki array sebanyak 1024 elemen, kasus terburuk menghasilkan pembandingan array sebanyak log₂ 1024 = 10 kali. Bandingkan dengan linear search yang pada kasus terburuknya melakukan pembandingan sebanyak 1024. Tentunya algoritma binary search menjadi lebih cepat. Namun jika data yang ada merupakan data yang tidak terurut maka akan jauh lebih cepat jika menggunakan linear search. Jika menggunakan binary search maka akan ada cost tambahan yaitu mengurutkan array terlebih dahulu. Algoritma binary search biasa di gunakan untuk database. Pada database tidak perlu ada algoritma sorting karena pada database sendiri sudah disediakan fungsi sorting baik untuk menaik atau menurun. Untuk lebih lengkapnya silahkan unduk di bawah ini.

download document