VISUALISASIKAN proses pencariannya.
Ket. : tidak perlu animatif/berbasis GUI, cukup dalam mode teks.
____________
Note: masih soal dari sepupu, dan masih ada lagi
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 Biner diimplementasikan pada fungsi binary_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.
