Binary Search - Phyton

Assalamualaikum wr.wb

woke kali ini, ane bakalan membeberkan salah satu algoritma Divide and Conquer atau dalam bahasanya adalah Bagi dan Selesaikan yaitu BINARY SEARCH (Pencarian Biner). Algoritma ini tidak termasuk kedalam algoritma brute force karena keefisienannya dalam mengurangi penggunaan memori apabila datanya yang tidak tergolong sedikit.

Pencarian Biner (Binary Search) dilakukan untuk :

• memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
• Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

Syarat utama dalam penggunaan binary search adalah data yang digunakan mesti Terurut. mau itu Ascending maupun Descending.

Pseucodenya :

 //Deklarasi
 data = dalam bentuk array terurut
 batasbawah = 0 
 batasatas = banyaknya data
 ketemu = False
 //Input angka yang ingin dicari
 cari = input()
 while (batasbawah <= batasatas) do
   tengah = (l + batasatas) div 2  
   nilaitengah = data[tengah])  
   if (knilaitengah > cari) then
     batasatas = tengah - 1  
   else if (nilaitengah < cari) then
     batasbawah = tengah + 1  
   else 
     ketemu = True
   end if
 end while

berikut tadi barusan pseucodenya... nah ane udh mengubahnya ke dalam bentuk phyton dan ini sesuai dengan pseucodenya.

 def BinarySearch(data):   
   //Example data = [1,2,4,5,8,12,24,56]  
   l = 0  
   h = len(d1)-1  
   cari = 5  
   while (l<=h):  
     mid = (l + h) //2  
     key = int(d1[mid])  
     if (key > cari):  
       h = mid - 1  
     elif (key < cari) :  
       l = mid + 1  
     else :  
       return True  
   return False  

contoh penggunaan binary search. kita ingin mencari angka 11

• Apakah angka lebih besar dari 8? (Ya)
• Apakah angka lebih besar dari 12? (Tidak)
• Apakah angka lebih besar dari 10? (Ya)
• Apakah angkat lebih besar dari 11? (Tidak)
• kalau ketemu kembalikan Ketemu = True, kalu tidak kembalikan nilai menjadi False.

berikut binary search atau pencarian biner. apabila ada pertanyaan yang ingin diajukan silahkan tulis di komentar :D.

Wassalamualaikum wr.wb

Read More