Skip to content

Pesona Informatika

Belajar programming, tech tips, dan catatan teknik informatika

Menu
  • Home
  • Android
  • Programming
    • Belajar Python
    • Belajar c++
    • Kumpulan contoh program Java
    • Belajar CSS Pemula Dari Awal
    • Belajar JavaScript
    • Belajar ReactJS
  • Operating System
  • Tips&Trick
  • Other Notes
Menu
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++

Feri Lukmansyah
Feri Lukmansyah

people who use linux and people who are friendly

Like our page, please… :D

Pesonainformatika

Sebuah site  untuk menyimpan dan dokumentasi apapun yang kami pelajari yang berhubungan dengan teknologi komputer khususnya pemrograman dan tentang perkuliahan.

©2023 Pesona Informatika | Design: Newspaperly WordPress Theme
Go to mobile version