Binary Search

Membagi dua ruang pencarian di setiap langkah dengan membandingkan target dengan elemen tengah. Koleksinya harus sudah terurut.

Kompleksitas

Waktu (Terbaik)

O(1)

Waktu (Rata-rata)

O(log n)

Waktu (Terburuk)

O(log n)

Memori

O(1)

Poin Penting

›Input harus terurut; tidak bisa dipakai pada data yang belum terurut
›Setiap perbandingan membuang setengah dari sisa ruang pencarian
›O(log n) jauh lebih cepat dibanding O(n) untuk input besar
›Hitung mid dengan low + (high - low) / 2 untuk menghindari integer overflow
›Polanya berlaku untuk banyak soal: mencari kemunculan pertama/terakhir, kondisi batas

Contoh Kode

Swift

func binarySearch(_ arr: [Int], target: Int) -> Int? {
    var low = 0, high = arr.count - 1
    while low <= high {
        let mid = low + (high - low) / 2
        if      arr[mid] == target { return mid }
        else if arr[mid] < target  { low  = mid + 1 }
        else                       { high = mid - 1 }
    }
    return nil
}

let sorted = [1, 3, 5, 7, 9, 11, 13, 15]
if let idx = binarySearch(sorted, target: 7) {
    print("Found at index \(idx)")  // Found at index 3
}

Latihan Soal

Binary Search

MudahLeetCode ↗

First Bad Version

MudahLeetCode ↗

Search a 2D Matrix

SedangLeetCode ↗

Find Minimum in Rotated Sorted Array

SedangLeetCode ↗