Buatlah sebuah program (Python/Java) yang dapat menghasilkan 50 bilangan bulat

Berikut ini adalah pertanyaan dari qed pada mata pelajaran TI untuk jenjang Sekolah Dasar

Buatlah sebuah program (Python/Java) yang dapat menghasilkan 50 bilangan bulat acak pada rentang 500 hingga 1000, menyimpannya ke dalam array/list, dan kemudian mencari sebuah bilangan dari array/list tersebut sesuai input user dengan algoritma Pencarian Biner.VISUALISASIKAN proses pencariannya.
Ket. : tidak perlu animatif/berbasis GUI, cukup dalam mode teks.
____________
Note: masih soal dari sepupu, dan masih ada lagi

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

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.

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Fri, 28 Oct 22