Belajar Algoritm - Binary Search & Variannya

#Pendahuluan

Setelah di episode 7 kita menutup FASE 2 dengan lower bound sorting, pada episode ini kita memulai FASE 3: SEARCHING & DIVIDE & CONQUER dengan Binary Search — salah satu algoritma paling powerful dan versatile dalam ilmu komputer. Dengan O(log n) waktu, Binary Search bisa menemukan elemen di array 1 miliar dalam 30 langkah saja.

Menguasai Binary Search bukan sekadar menghafal template — kalian harus memahami loop invariant di baliknya, sehingga bisa memodifikasinya untuk varian yang lebih kompleks. Episode ini membahas bukan hanya binary search klasik, tetapi lima varian yang sering muncul di coding interview dan production.

#Binary Search Klasik

Binary search membagi search space menjadi dua di setiap langkah: jika target lebih kecil dari tengah, cari di kiri; jika lebih besar, cari di kanan.

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

#Loop Invariant

• Inisialisasi: low = 0, high = len(arr) - 1 — target jika ada pasti di arr[low..high].
• Maintenance: setiap iterasi, search space diperkecil tetapi invariant terjaga — target jika ada tetap di arr[low..high].
• Termination: ketika low > high, search space kosong → target tidak ada → return -1.

#Varian 1: First & Last Occurrence

Binary search klasik menemukan salah satu kemunculan. Untuk menemukan kemunculan pertama atau terakhir, modifikasi agar tetap mencari meskipun sudah ketemu.

def find_first(arr, target):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1  # cari lebih kiri
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result
 
def find_last(arr, target):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            result = mid
            low = mid + 1  # cari lebih kanan
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

Kunci: saat menemukan target, jangan langsung return — simpan hasil dan lanjutkan pencarian ke arah yang sesuai.

#Varian 2: Lower & Upper Bound

Lower bound = index pertama di mana arr[i] >= target. Upper bound = index pertama di mana arr[i] > target.

def lower_bound(arr, target):
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low
 
def upper_bound(arr, target):
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

Perhatikan perbedaan: lower bound menggunakan < dan upper bound menggunakan <=. Jumlah kemunculan target = upper_bound - lower_bound.

#Varian 3: Search in Rotated Sorted Array

Array terurut yang di-rotate (misal [4,5,6,7,0,1,2]). Binary search dimodifikasi: tentukan sisi mana yang terurut, lalu tentukan apakah target ada di sisi terurut tersebut.

def search_rotated(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        # Kiri terurut
        if arr[low] <= arr[mid]:
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # Kanan terurut
        else:
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

#Varian 4: Answer Binary Search

Answer binary search digunakan ketika kita mencari nilai minimum/maximum yang memenuhi kondisi tertentu — bukan mencari elemen di array, tetapi mencari jawaban di space yang bisa di-binary-search.

def min_capacity(weights, days):
    """Cari kapasitas minimum supaya semua paket bisa dikirim dalam days hari"""
    def can_ship(capacity):
        days_needed = 1
        current = 0
        for w in weights:
            if current + w > capacity:
                days_needed += 1
                current = 0
            current += w
        return days_needed <= days
 
    low = max(weights)
    high = sum(weights)
    while low < high:
        mid = low + (high - low) // 2
        if can_ship(mid):
            high = mid
        else:
            low = mid + 1
    return low

Pola: search space adalah range jawaban yang mungkin; predicate function menentukan apakah suatu jawaban valid; binary search menemukan jawaban optimal.

#Praktik

1. Implementasi "find first & last position" — leetcode 34.
2. Implementasi "search in rotated sorted array" — leetcode 33.
3. Latihan 3 answer-binary-search problems: kapasitas minimum, Koko eating bananas, split array largest sum.

#Penutup

Pada episode 8 ini, kalian telah memahami:

• Binary search klasik: O(log n) dengan loop invariant yang kuat.
• First/last occurrence: modifikasi untuk mencari batas kemunculan.
• Lower/upper bound: finding position insertion point.
• Rotated sorted array: menentukan sisi terurut terlebih dahulu.
• Answer binary search: mencari optimal value dengan predicate function.

Di episode 9 selanjutnya kita akan membahas Divide & Conquer Lanjut — aplikasi seperti closest pair of points O(n log n), Strassen matrix multiplication, dan overview Cooley-Tukey FFT. Sampai jumpa di episode 9!