Penerapan Algoritma Pencarian Biner (Binary Search) di Excel

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.

Be the first to comment

Leave a Reply

Your email address will not be published.


*