Alogoritma Binary Search Menggunakan Python – pesonainformatika.com terdapat beberapa algoritma untuk melakukan pencarian pada suatu data salah satunya adalah binary search, binary search adalah algorima untuk menemukan item di dalam list yang sudah diurutkan.
Cara Kerja Binary Search
cara kerjanya cukup simple yaitu dengan cara membagi setengah dari list angka yang akan dihitung secara berulang, misalnya kita punya list seperti ini
[1, 3, 5, 6, 7, 12, 13]
disini umumnya pencarian suatu item biasa dimulai kiri ke kanan namun dengan binary search ini akan dipecah dulu menjadi beberapa bagian sehingga mempercepat proses pencarian disini saya akan memberikan contoh perbedaan menggunakan binary search dan menggunakan pencarian biasa (naive search)
Membuat Fungsi pencarian Biasa
disini kita akan membuat fungsi untuk mencari item disuatu list dengan menerapkan logika pencarian dari kiri ke kanan misal seperti ini
def naive_search(data: list, target: int):
for i in range(len(data)):
if data[i] == target:
return i
return -1
nah fungsi ini akan mencari targat dari kiri ke kanan jika kita jalankan dengan fungsi seperti ini
def main():
data_list: list = [1, 3, 5, 6, 7, 12, 13]
target: int = 12
result = naive_search(data=data_list, target=target)
print(result)
if __name__ == '__main__':
main()
maka hasilnya seperti ini
sekarang kita akan membuat fungsi untuk mengimplementasikan binary search seperti ini
Membuat Implentasi Binary Search
sekarang coba buat fungsi baru untuk implementasi binary search
# binary search
def binary_search(data: list, target: int, low=None, high=None):
if low is None:
low = 0
if high is None:
high = len(data) - 1
if high < low:
return -1
# Get Midpoint
midpoint = (low + high) // 2
if data[midpoint] == target:
return midpoint
elif target < data[midpoint]:
new_high = midpoint - 1
return binary_search(data, target, low, new_high)
else:
new_low = midpoint + 1
return binary_search(data, target, new_low, high)
bila kita jalankan maka hasilnya sama
def main():
data_list: list = [1, 3, 5, 6, 7, 12, 13]
target: int = 12
result = binary_search(data=data_list, target=target)
print(result)
lalu apa bedanya? disini akan saya jelaskan perbedaannya terletak pada kecepatan dalam mencari angka misal kita bisa hitung menggunakan modul time seperti ini
def main():
length: int = 10000
sorted_list = set()
while len(sorted_list) < length:
sorted_list.add(random.randint(-3 * length, 3 * length))
sorted_list = sorted(list(sorted_list))
target_list = [random.randint(-3 * length, 3 * length) for _ in range(length)]
# counting naive search
start = time.time()
for target in target_list:
naive_search(sorted_list, target)
end = time.time()
print(f'Naive Search Time: {(end - start)} Seconds')
# counting binary search
start = time.time()
for target in target_list:
binary_search(sorted_list, target)
end = time.time()
print(f'Binary Search Time: {(end - start)} Seconds')
if __name__ == '__main__':
main()
jika dijalankan maka akan terjadi perbedaan waktu perhitungan yang siknifikan seperti ini
baik sampai disini pembahasan kali ini semoga bermanfaat dan selamat mencoba source code dapat di download disini, ikuti terus pesonainformatika, dan dapatkan studi kasus bahasa pemrograman lainya seperti Java, Python C++
people who use linux and people who are friendly