Praktikum Algoritma: Binary Search dengan Python 🚀🔍

Halo lagi, teman-teman mahasiswa! Setelah kemarin kita seru-seruan dengan Linear Search (yang cek satu-satu kayak nyari jarum di tumpukan jerami), sekarang kita naik level ke Binary Search – si pintar yang super cepat!

Bayangkan kamu lagi buka kamus tebal buat cari kata "Python". Kamu nggak mulai dari halaman 1, kan? Langsung buka tengah-tengah, lihat apakah kata itu di kiri atau kanan, terus potong lagi setengahnya. Nah, itu persis binary search! Cocok banget buat data yang sudah terurut (sorted). Yuk kita pelajari bareng, santai tapi keren! 😎

Ilustrasi di atas nunjukin gimana binary search "memotong" array terus-menerus sampai ketemu target. Keren banget visualnya!

Apa Itu Binary Search? 🤩

Binary search adalah algoritma pencarian yang membagi dua (divide and conquer) daftar yang sudah terurut berkali-kali sampai menemukan target.

• Setiap langkah: Hitung tengah (mid), bandingkan dengan target.
  • Kalau sama → Ketemu!
  • Kalau target lebih kecil → Cari di bagian kiri.
  • Kalau target lebih besar → Cari di bagian kanan.
• Kalau bagiannya kosong → Nggak ketemu.

Kelebihan: Super cepat! Untuk 1 juta data, paling banyak cuma sekitar 20 langkah aja.
Kekurangan: Harus data sudah terurut dulu. Kalau acak, nggak bisa dipakai.

Cara Kerja Binary Search Langkah demi Langkah 📊

Contoh array terurut: [10, 20, 30, 40, 50, 60, 70, 80]

Target: 50

1. Low = 0, High = 7 → Mid = (0+7)//2 = 3 → arr[3] = 40 < 50 → Cari kanan (Low = 4)
2. Low = 4, High = 7 → Mid = 5 → arr[5] = 60 > 50 → Cari kiri (High = 4)
3. Low = 4, High = 4 → Mid = 4 → arr[4] = 50 == 50 → Ketemu di index 4!

Kalau target 25: Akhirnya low > high → Nggak ketemu.

Gambar ini detail banget step-by-stepnya, kayak lagi main tebak-tebakan angka!

Visual sederhana ini bikin langsung ngerti proses pembagiannya.

Implementasi di Python 🐍

Ada dua cara keren: Iteratif (pakai while loop, lebih hemat memori) dan Rekursif (elegan tapi bisa stack overflow kalau data terlalu besar).

Versi Iteratif (Rekomendasi buat pemula)

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Nggak ketemu

Versi Rekursif (Bonus keren)

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low > high:
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

Contoh 1: Cari Angka di List Bilangan Bulat 👍

daftar_angka = [5, 12, 23, 34, 45, 56, 67, 78, 89, 100]
target = 45

hasil = binary_search(daftar_angka, target)
if hasil != -1:
    print(f"Yess! {target} ketemu di index {hasil}")
else:
    print(f"{target} nggak ada nih 😅")

Output: Yess! 45 ketemu di index 4

Contoh 2: Cari Kata di List String (Nama Kota Terurut)

kota = ["Bandung", "Jakarta", "Medan", "Semarang", "Surabaya", "Yogyakarta"]
target = "Semarang"

hasil = binary_search(kota, target)
if hasil != -1:
    print(f"Kota {target} ada di urutan ke-{hasil + 1} (index {hasil})")
else:
    print("Kota misterius, nggak ada di list 📍")

Output: Kota Semarang ada di urutan ke-4 (index 3)

Contoh 3: Nggak Ketemu

angka = [10, 20, 30, 40, 50]
target = 35

print(binary_search(angka, target))  # Output: -1

Contoh 4: Target di Awal, Tengah, atau Akhir

listku = [1, 3, 5, 7, 9, 11, 13]

print(binary_search(listku, 1))   # 0 (awal)
print(binary_search(listku, 7))   # 3 (tengah)
print(binary_search(listku, 13))  # 6 (akhir)

Bonus: Bandingkan dengan Linear Search ⚡

Binary search jauh lebih cepat untuk data besar!

Infografis ini nunjukin perbedaan jelas: Linear cek semua, Binary potong setengah-setengah. Mind blowing!

Latihan Seru Buat Kamu! 💥

1. Coba pakai versi rekursif di contoh-contoh atas.
2. Buat fungsi yang menghitung berapa langkah yang dibutuhkan sampai ketemu.
3. Timing test: Buat list besar (pakai sorted(range(1000000))) dan bandingkan waktu linear vs binary search pakai module time.
4. Modifikasi biar bisa cari duplikat (kembalikan semua index kalau ada lebih dari satu).

Selamat praktikum, guys! Binary search ini fondasi penting buat algoritma lebih advanced. Kalau sudah paham, kamu bakal merasa kayak superhero programmer 🤖✨ Coba-coba sendiri di Python, kalau stuck tanya aja. Keep coding and have fun! 🎉🐍