Binary Search

Linear search bekerja pada data apa pun, tetapi lambat untuk dataset besar. Binary search memanfaatkan fakta bahwa array sudah terurut untuk memangkas setengah kandidat setiap iterasi. Hasilnya: kompleksitas turun dari O(n) menjadi O(log n). Pada n = 1.000.000, linear search rata-rata membandingkan 500.000 elemen, sedangkan binary search paling banyak 20 perbandingan. Pada chapter ini kita akan mengimplementasikan binary search dalam dua versi (iteratif dan rekursif), lalu membandingkannya dengan fungsi standar bsearch() dari <stdlib.h>.

Cara Kerja Binary Search #

Prasyarat binary search: array harus terurut (menaik atau menurun). Algoritma memelihara dua pointer, kiri dan kanan, yang menandai batas kandidat pencarian. Pada setiap langkah, algoritma membandingkan elemen tengah dengan target:

• Bila elemen tengah sama dengan target, kembalikan indeks tengah.
• Bila elemen tengah lebih kecil, target pasti di setengah kanan—pindahkan kiri ke mid + 1.
• Bila elemen tengah lebih besar, target pasti di setengah kiri—pindahkan kanan ke mid - 1.

Setiap iterasi memangkas setengah kandidat, sehingga loop paling banyak berjalan log2(n) + 1 kali.

Visualisasi Konsep #

Diagram berikut memperlihatkan bagaimana binary search mencari target 23 pada array 10 elemen terurut dengan memangkas setengah kandidat di setiap iterasi:

Pada diagram di atas, binary search memangkas setengah kandidat di setiap iterasi. Iterasi pertama menghitung mid = 4 dan menemukan a[4] = 16 yang lebih kecil dari target 23, sehingga rentang kandidat dipangkas dari 10 elemen menjadi 5 elemen (indeks 5-9). Iterasi kedua menghitung mid = 7 dan menemukan a[7] = 56 yang lebih besar dari target, sehingga rentang dipangkas lagi menjadi 2 elemen (indeks 5-6). Iterasi ketiga menghitung mid = 5 dan menemukan a[5] = 23 sama dengan target—pencarian selesai. Kompleksitas O(log n) muncul karena setiap iterasi memangkas setengah kandidat: untuk n = 10 elemen dibutuhkan paling banyak 4 iterasi (log2(10) ≈ 3.32), sedangkan linear search rata-rata membandingkan 5 elemen.

Versi Iteratif dan Rekursif #

Kita akan menulis dua versi binary search dengan logika yang sama. Versi iteratif menggunakan loop while, sedangkan versi rekursif memanggil dirinya sendiri dengan rentang lebih sempit.

#include <stdio.h>

/* Binary search iteratif pada array terurut */
int binary_search_iter(const int *a, int n, int target) {
    int kiri = 0, kanan = n - 1;
    while (kiri <= kanan) {
        int mid = kiri + (kanan - kiri) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) kiri = mid + 1;
        else kanan = mid - 1;
    }
    return -1;
}

/* Binary search rekursif */
int binary_search_rec(const int *a, int kiri, int kanan, int target) {
    if (kiri > kanan) return -1;
    int mid = kiri + (kanan - kiri) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binary_search_rec(a, mid + 1, kanan, target);
    return binary_search_rec(a, kiri, mid - 1, target);
}

int main(void) {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(a) / sizeof(a[0]);

    int target[] = {23, 91, 2, 99, 8};
    printf("Iteratif:\n");
    for (int i = 0; i < 5; i++) {
        int idx = binary_search_iter(a, n, target[i]);
        if (idx == -1)
            printf("  target %2d tidak ditemukan\n", target[i]);
        else
            printf("  target %2d ditemukan di indeks %d\n", target[i], idx);
    }

    printf("\nRekursif:\n");
    for (int i = 0; i < 5; i++) {
        int idx = binary_search_rec(a, 0, n - 1, target[i]);
        if (idx == -1)
            printf("  target %2d tidak ditemukan\n", target[i]);
        else
            printf("  target %2d ditemukan di indeks %d\n", target[i], idx);
    }
    return 0;
}

Output yang Dihasilkan:

Iteratif:
  target 23 ditemukan di indeks 5
  target 91 ditemukan di indeks 9
  target  2 ditemukan di indeks 0
  target 99 tidak ditemukan
  target  8 ditemukan di indeks 2

Rekursif:
  target 23 ditemukan di indeks 5
  target 91 ditemukan di indeks 9
  target  2 ditemukan di indeks 0
  target 99 tidak ditemukan
  target  8 ditemukan di indeks 2

Kedua versi menghasilkan output identik. Versi iteratif dan rekursif memiliki kompleksitas O(log n) waktu dan O(1) / O(log n) ruang tambahan. Versi iteratif lebih hemat memori karena tidak menggunakan call stack.

Mari kita telaah baris-baris kode di atas:

1. Baris 5 (int kiri = 0, kanan = n - 1;): inisialisasi rentang pencarian ke seluruh array.
2. Baris 6 (while (kiri <= kanan)): loop berlanjut selama masih ada kandidat. Bila kiri > kanan, berarti target tidak ada dan loop berhenti.
3. Baris 7 (int mid = kiri + (kanan - kiri) / 2;): menghitung indeks tengah dengan rumus kiri + (kanan - kiri) / 2 alih-alih (kiri + kanan) / 2. Trik ini menghindari integer overflow bila kiri + kanan melebihi INT_MAX.
4. Baris 8-9 (if (a[mid] == target) return mid;): bila elemen tengah adalah target, kembalikan indeks langsung.
5. Baris 10 (if (a[mid] < target) kiri = mid + 1;): bila elemen tengah lebih kecil dari target, target pasti di setengah kanan—pindahkan batas kiri.
6. Baris 11 (else kanan = mid - 1;): sebaliknya, target di setengah kiri—pindahkan batas kanan.
7. Baris 13 (return -1;): bila loop keluar tanpa menemukan target, kembalikan -1.
8. Baris 17-23 (binary_search_rec): versi rekursif. Base case kiri > kanan mengembalikan -1. Case rekursif memilih separuh rentang untuk dipanggil rekursif.

Menggunakan bsearch() Standar #

Standard library C menyediakan fungsi generik bsearch() dari <stdlib.h>. Fungsi ini menerima callback comparator sehingga dapat dipakai untuk array tipe apa pun—tidak hanya int. Berikut contoh pemakaiannya pada array integer.

#include <stdio.h>
#include <stdlib.h>

/* Bandingkan dua int untuk bsearch */
static int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return (a > b) - (a < b);
}

int main(void) {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    size_t n = sizeof(a) / sizeof(a[0]);

    int target[] = {23, 91, 99, 2};
    for (int i = 0; i < 4; i++) {
        int *found = (int *)bsearch(&target[i], a, n, sizeof(int), cmp_int);
        if (found == NULL) {
            printf("target %2d tidak ditemukan (bsearch)\n", target[i]);
        } else {
            printf("target %2d ditemukan di indeks %ld (bsearch)\n",
                   target[i], found - a);
        }
    }
    return 0;
}

Output yang Dihasilkan:

target 23 ditemukan di indeks 5 (bsearch)
target 91 ditemukan di indeks 9 (bsearch)
target 99 tidak ditemukan (bsearch)
target  2 ditemukan di indeks 0 (bsearch)

Fungsi bsearch() menerima callback cmp_int yang membandingkan dua int lewat pointer generik const void *. Pola perbandingan (a > b) - (a < b) menghasilkan -1, 0, atau 1 tanpa risiko overflow, berbeda dengan a - b yang overflow bila a positif besar dan b negatif besar. bsearch() mengembalikan pointer ke elemen yang ditemukan (atau NULL), sehingga kita bisa menghitung indeksnya dengan found - a.

Kompleksitas dan Batasan #

Tabel berikut merangkum kelas kompleksitas binary search: