Alogoritma Binary Search Menggunakan Python - pesonainformatika.com

Alogoritma Binary Search Menggunakan Python

Posted on

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

Alogoritma Binary Search Menggunakan Python - pesonainformatika.com
hasil fungsi naive search

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)
implementasi binary search

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

hasil perbandingan kecepatan perhitungan naive dan binary search

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++