Kode Program (Python)

# binarysearch.py
# Program oleh HY
import random
iterator = 0
# Wrapper function untuk binary search
def binary_search(data, x):
   # data: array/list yang sudah terurut
   def binary_search_internal(data, bawah, atas, x):
       globals()['iterator'] += 1
       if atas >= bawah:
           tengah = (atas + bawah) // 2
           print("=================================")
           print("Langkah ke-" + str(iterator))
           if atas == bawah or atas-bawah+1 <= 5:
               print("data = " + str(data[bawah:atas+1]))
           else:
               print("data = [{db:d}, ..., {dtmin:d}, {dt:d}, {dtplus:d}, ..., {da:d}]"
                   .format(db = data[bawah],
                       dtmin = data[tengah-1],
                       dtplus = data[tengah+1],
                       dt = data[tengah],
                       da = data[atas-1]
                           if atas == len(data) else data[atas]))
           if data[tengah] == x:
               print("==>  {dt:d} = {xval:d}"
                   .format(dt = data[tengah], xval = x))
               return tengah
           elif data[tengah] > x:
               print("==>  {dt:d} > {xval:d}"
                   .format(dt = data[tengah], xval = x))
               print("==>  Pencarian Biner di subarray kiri")
               return binary_search_internal(data, bawah, tengah - 1, x)
           else:
               print("==>  {dt:d} < {xval:d}"
                   .format(dt = data[tengah], xval = x))
               print("==>  Pencarian Biner di subarray kanan")
               return binary_search_internal(data, tengah + 1, atas, x)
       else:
           return -1
   # end of binary_search_internal()
   return binary_search_internal(data, 0, len(data), x)
# end of binary_search()
### Program Utama ###
if __name__ == '__main__':
   system("clear")
   print()
   data = random.sample(range(500, 1000), 50)
   sorted_data = data.copy()
   sorted_data.sort()
   print("data (terurut) = " + str(sorted_data), end="\n\n")
   x = int(input("Data yang ingin dicari: "))
   print()
   hasil = binary_search(sorted_data, x)
   print("=================================")
   if hasil != -1:
       print("\n{xval:d} ditemukan pada elemen ke-{idx:d} dari data terurut,\natau pada elemen ke-{idx2:d} pada data asli.\n"
           .format(xval = x, idx = hasil, idx2 = data.index(x)))
   else:
       print("\n{xval:d} tidak ditemukan.\n"
           .format(xval = x))
### END OF __main__ ###

_______________

Pembahasan

Pada program di atas, algoritma utama Pencarian Binerdiimplementasikan pada fungsibinary_search_internal(data, bawah, atas, x). Karena harus menampilkan visualisasi proses pencarian, maka dalam fungsi tersebut juga disertakan kode program untuk menampilkan output.

Pada dasarnya, implementasi algoritma Pencarian Biner pada program di atas adalah:
def binary_search(data, bawah, atas, x):
   if atas >= bawah:
       if data[tengah] == x:
           return tengah
       elif data[tengah] > x:
           return binary_search(data, bawah, tengah - 1, x)
       else:
           return binary_search(data, tengah + 1, atas, x)
   else:
       return -1

Contoh Hasil Eksekusi Program

(data random)

data (terurut) = [507, 509, 512, 552, 554, 586, 598, 602, 604, 610, 619, 631, 638, 646, 653, 662, 667, 668, 672, 677, 694, 702, 730, 747, 757, 809, 815, 834, 842, 845, 846, 850, 854, 868, 879, 893, 895, 897, 903, 904, 907, 908, 911, 912, 914, 915, 938, 949, 957, 974]

Data yang ingin dicari: 604

=================================
Langkah ke-1
data = [507, ..., 757, 809, 815, ..., 974]
==>  809 > 604
==>  Pencarian Biner di subarray kiri
=================================
Langkah ke-2
data = [507, ..., 631, 638, 646, ..., 757]
==>  638 > 604
==>  Pencarian Biner di subarray kiri
=================================
Langkah ke-3
data = [507, ..., 554, 586, 598, ..., 631]
==>  586 < 604
==>  Pencarian Biner di subarray kanan
=================================
Langkah ke-4
data = [598, ..., 602, 604, 610, ..., 631]
==>  604 = 604
=================================

604 ditemukan pada elemen ke-8 dari data terurut,
atau pada elemen ke-43 pada data asli.