Membuat Program Binary Search di Bahasa Pemrograman Python

Binary Search adalah salah satu metode pencarian atau pengecekan sebuah elemen angka di dalam sebuah wadah. Jika di dalam wadah terdapat elemen angka yang dicari oleh user, maka program tersebut akan mengembalikan statement True. Begitu pun sebaliknya, jika di dalam wadah tersebut tidak terdapat elemen angka yang dicari oleh user maka program tersebut akan mengembalikan statement False.

Point penting yang harus sobat perhatikan disini adalah metode ini hanya bisa digunakan untuk wadah dengan angka yang sudah urut (wadah dengan elemen angka dari kecil ke besar). Program ini akan sangat berguna ketika wadah yang user gunakan mengandung banyak sekali elemen angka di dalamnya.

Baiklah kita akan memulai pembahasan materi tentang bagaimana Membuat Program Binary Search di Bahasa Pemrograman Python. Silahkan cermati program di bawah ini :

1. def binSearch(wadahList,target) :
2.     low = 0
3.     high = len(wadahList)-1
4.     while low <= high :
5.         mid = (high+low)//2
6.         if target == wadahList[mid] :
7.             return True
8.         elif target < wadahList[mid] :
9.             high = mid - 1
10.         else :
11.             low = mid + 1
12.     return False

Keterangan :

1. Membuat function bernama binSearch(wadahList, target) dengan dua variable yaitu var wadahList mewakili wadah dan var target mewakili elemen angka yang ingin dicari.
2. Membuat var low dengan nilai 0.
   
   "Fungsi dari var low adalah untuk menentukan elemen angka pertama yang akan diindeks."
3. Membuat var high dengan nilai banyak elemen angka pada saat itu dan dikurangi dengan angka 1.
   
   "Fungsi dari var high adalah untuk menentukan elemen angka terakhir yang akan diindeks."
4. Looping dengan kondisi nilai dari var low kurang dari atau sama dengan nilai dari var high.
5. Membuat var mid dengan nilai hasil kalkulasi dari penjumlahan nilai var high dan var low kemudian hasil penjumlahan tersebut dibagi 2.
   
   "Nilai var high dan var low bisa berubah, lihat step 9 dan 11."
6. Jika nilai var target sama dengan nilai var wadahList dengan indeks nilai var mid, maka :
7. Mengembalikan statement True.
8. Jika nilai var target kurang dari nilai var wadahList dengan indeks nilai var mid, maka :
9. Nilai var high berubah menjadi nilai var mid dikurangi dengan angka 1.
10. Jika nilai var target kondisinya tidak sama dengan kedua kondisi (if dan elif) di atas, berarti nilai var target lebih besar dari nilai var wadahList dengan indeks var mid, maka :
11. Nilai var low berubah menjadi nilai mid ditambah dengan angka 1.
12. Mengembalikan statement False jika nilai var target tidak berada di dalam var wadahList.

Saya akan memberikan contoh beserta pengerjaan manual atau proses program ini berjalan. Silahkan sobat perhatikan contoh berikut :

A = [2,5,8,11,25,32,45,56,68,86,93]

Pada contoh di atas terdapat wadah bernama A dan didalamnya terdapat 11 elemen angka yang sudah berurutan dari kecil ke besar. 

Misalnya kita ingin mencari elemen angka dengan target = 68 maka :

2

5

8

11

25

32

45

56

68

86

93

• Program akan mengindeks elemen pertama yaitu angka 2, elemen akhir yaitu angka 93, dan elemen tengah yaitu angka 32.
• Perulangan program :
• Program akan membandingkan target dengan elemen tengah (32).
• Pada contoh tersebut kita bisa simpulkan bahwa 68 > 32, maka elemen awal akan berubah menjadi elemen dengan indeks tengah + 1 yaitu angka 45.
  Wadah akan berubah menjadi :

45

56

68

86

93

• Perulangan program :
• Program membandingkan lagi antara target dengan elemen tengah yang baru (68).
• Pada kasus ini kita bisa menyimpulkan bahwa target (68) = elemen tengah (68), maka program tersebut akan mengembalikan statement True.

Catatan :

Program akan terus melakukan perulangan sampai target bernilai sama dengan nilai elemen tengah. Kemudian program akan berhenti dan mengembalikan statement True. Jika program tidak menemukan kondisi nilai target sama dengan nilai elemen tengah, maka program akan berhenti dan mengembalikan statement False.

Contoh program setelah dieksekusi :

Demikian materi hari ini tentang bagaimana Membuat Program Binary Search di Bahasa Pemrograman Python. Semoga tulisan saya mudah dipahami oleh sobat semua, dan jika ingin mengajukan pertanyaan silahkan menulis di kolom komentar. Terimakasih :)