WANTED

Binary Search adalah salah satu algoritma pencarian yang tercepat. Kecepatan algoritma ini hanya bisa dikalahkan oleh teknik hashing, yang tidak akan dibahas di sini. Untuk mencari jutaan data, Binary Search hanya butuh O(log N) kali pembandingan (sekitar 20 kali), sedangkan Linier Search butuh O(N) pembandingan (sekitar 500.000 kali). Tapi yang harus dicatat di sini, data yang dicari harus sudah terurut!

Algoritma iteratif (contohnya yang menggunakan perputaran FOR, WHILE, dsb) pada umumnya dapat dengan mudah diubah ke dalam algoritma rekursif (memanggil dirinya sendiri). Keistimewaan algoritma iteratif adalah sederhana, cepat, dan menggunakan sedikit memori. Sedangkan pada kasus seperti menelusuri pohon, algoritma rekursif jelas lebih baik karena lebih mudah difahami.

Pada prinsipnya, Binary Search adalah membandingkan Key (angka yang dicari) dengan angka yang berada tepat di tengah-tengah deretan angka yang sudah terurut. Jika sama, maka itulah yang dicari. Tapi jika tidak sama, maka deretan data dipecah menjadi dua blok: Blok bawah (kecil) dan blok atas (kecil). Lalu proses diulangi terhadap blok bawah atau blok atas, tergantung besarnya Key apakah lebih kecil ataukah lebih besar daripada data yang berada di tengah-tengah tadi.

Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama. Berikut ini adalah pseudocode sederhana yang menentukan indeks (posisi) dari nilai yang diberikan dalam sebuah list berurut, a berada antara left dan right :

function binarySearch(a, value, left, right)

    if right < left

        return not found

    mid := floor((right-left)/2)+left

    if a[mid] = value

        return mid

    if value < a[mid]

        return binarySearch(a, value, left, mid-1)

    else

        return binarySearch(a, value, mid+1, right)

Karena pemanggilan fungsi di atas adalah rekursif ekor, fungsi tersebut dapat dituliskan sebagai sebuah pengulangan (loop), hasilnya adalah algoritma in-place:

function binarySearch(a, value, left, right)

    while left ≤ right

        mid := floor((right-left)/2)+left

        if a[mid] = value

            return mid

        if value < a[mid]

            right := mid-1

        else

            left  := mid+1

    return not found

Pada kedua kasus, algoritma akan berakhir karena paa setiap pemanggilan rekursif atau pengulangan, jangkauan indeks right dikurang left akan selalu mengecil, dan akhirnya pasti akan menjadi negatif.

Pencarian biner adalah sebuah algoritma logaritmik dan bekerja dalam waktu O(log n). Secara khusus, 1 + log₂N pengulangan yang diperlukan untuk menghasilkan jawaban. Hal ini dianggap lebih cepat dibandingkan sebuah pencarian linear. Pencarian biner dapat diimplementasikan dengan rekursi atauiterasi, seperti yang terlihat di atas, walaupun pada kebanyakan bahasa pemrograman akan lebih elegan bila dinyatakan secara rekursif.