Bayangkan jika kita harus menebak angka dari 1 sampai 100, disetiap tebakan kita akan diberitahu jika lebih kecil atau lebih besar dari hasil tebakan kita.
Jika kita asal menebak, kita akan menebak sembarang angka dan jumlah tebakan kita bisa sangat banyak sekali karena kita tidak tahu angka tebakannya berapa. Mungkin dimulai dari menebak angka 1 kemudian 2 dan seterusnya, sampai tebakannya benar.
Langkah tercepat untuk menebak angka seperti diatas adalah dengan membagi 2 jumlah datanya, jika 1-100 maka tebakan pertama adalah 50 jika angkanya lebih lebih tinggi maka hasilnya dibagi 2 kembali yaitu 75 jika angkanya lebih kecil, tebakan angka berada di antara 50 dan 75 , begitu seterusnya sampai kita menebak angkanya.
Cara diatas adalah gambaran dari Algoritma Binary search atau Pencarian Biner. Prinsip dari pencarian Biner bisa dijelaskan sebagai berikut.
Cari posisi awal (0) dan posisi akhir (N -1) , kemudian cari nilai tengah dengan rumus (posisi awal + posisi akhir) / 2. Nilai yang dicari kemudian dibandingkan dengan Nilai tengah. Jika lebih kecil, proses dilanjutkan kembali tetapi posisi akhir dianggap sama dengan posisi tengah – 1. Jika lebih besar, proses dilanjutkan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan nilai yang dicari.
Untuk lebih jelasnya, kita buat dengan contoh. Misalnya kita ingin mencari angka 9 dari urutan data berikut.
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Salah satu syarat agar pencarian biner dapat dilakukan adalah data harus dalam keadaan urut
Mula-mula cari data tengan dengan rumus (0+9)/2 = 4 , dari data diatas Index Data ke 4 adalah 5. Karena 9 lebih besar dari 5, maka daftar datanya menjadi seperti ini
[ 6, 7, 8, 9, 10]
Nilai tengah dari data diatas adalah 8. 9 masih lebih besar dari 8 maka daftar nilainya menjadi seperti ini
[ 9, 10]
Nilai tengah sekarang bernilai 9, Nilai yang dicari sudah ditemukan. dan pencarian dihentikan.
Membuat Fungsi UDF dari Binary Search
Sekarang kita coba terapkan algoritma pencarian biner pada rumus Excel dengan membuat fungsi UDF dengan VBA.
Disini kita akan membuat sebuah Rumus dengan 2 parameter. Parameter pertama adalah Array (Range) dan Paremeter kedua adalah nilai yg dicari, hasilnya akan mengembalikan index dari array yang dicari.
Function BinarySearch(LData As Variant, nCari As Variant) As Integer
' Auth : Excelnoob
' Fungsi : Binary Search UDF
'--------------------------------------
Dim nBawah As Integer
Dim nTengah As Integer
Dim nAtas As Integer
Dim cArray As Variant
cArray = Application.Transpose(LData)
nBawah = LBound(cArray)
nAtas = UBound(cArray)
Do While nBawah < nAtas
nTengah = (nBawah + nAtas) \ 2
If nCari = cArray(nTengah) Then
nBawah = nTengah
Exit Do
ElseIf nCari > cArray(nTengah) Then
nBawah = nTengah + 1
Else
nAtas = nTengah - 1
End If
Loop
If cArray(nBawah) = nCari Then
BinarySearch = nBawah
Else
BinarySearch = -1 'Jika tidak ditemukan
End If
End Function
Selain itu, untuk melihat berapa kali jumlah looping yang dilakukan, kita juga bisa membuat UDF untuk mengetahui hal tersebut. berikut ini adalah script untuk menghitung jumlah looping nya
Function BinarySearchLoop(LData As Variant, nCari As Variant) As Integer
' Auth : Excelnoob
' Fungsi : Binary Search UDF Jml looping
'--------------------------------------
Dim nBawah As Integer
Dim nTengah As Integer
Dim nAtas As Integer
Dim cArray As Variant
Dim Jml As Long
cArray = Application.Transpose(LData)
nBawah = LBound(cArray)
nAtas = UBound(cArray)
Do While nBawah < nAtas
nTengah = (nBawah + nAtas) \ 2
If nCari = cArray(nTengah) Then
nBawah = nTengah
Exit Do
ElseIf nCari > cArray(nTengah) Then
nBawah = nTengah + 1
Else
nAtas = nTengah - 1
End If
Jml = Jml + 1
Loop
BinarySearchLoop = Jml + 1
End Function
Berikut ini adalah contoh penerapan pada rumus Excel
Demikianlah sedikit gambaran dari penggunakan Binary search pada Rumus Excel yang dibuat dengan Macro VBA.
Leave a Reply