Mayoritas bug pada algoritma DSA bukan muncul di input rata-rata, tetapi di batas: array kosong, satu elemen, elemen maksimum/minimum, atau input yang sudah terurut. Edge case testing adalah disiplin memilih dan menguji input batas tersebut secara eksplisit. Pada Chapter ini kita akan memetakan kategori edge case wajib, membedah tiga bug klasik (integer overflow, off-by-one, mid-overflow pada binary search), dan menulis harness yang menjalankan semua edge case sekaligus. Tujuan akhirnya: daftar edge case yang dapat dipakai ulang untuk semua algoritma sejenis.

Kategori Edge Case Wajib #

KategoriContohMengapa Berbahaya
Kosong{}Loop tidak dieksekusi; inisialisasi best = a[0] UB bila a kosong
Satu elemen{7}Loop body di-skip; indeks 0 diakses tanpa validasi
Maksimum/minimumINT_MAX, INT_MINOverflow pada +, *
Negatif semua{-5,-2,-8}Inisialisasi best = 0 mengembalikan jawaban salah
Sudah sorted{1,2,3,4,5}Quicksort naif → O(n²)
Reverse sorted{5,4,3,2,1}Worst case quicksort, stack overflow rekursi dalam
Duplikat{3,3,3,3}Bug pada deduplikasi, partition, atau pemilihan pivot
Target di ujungtarget = elemen pertama/terakhirOff-by-one pada batas loop

Mekanisme: Tiga Bug Klasik #

1. Integer Overflow #

Operasi a + b pada int (32-bit signed) overflow bila a + b > INT_MAX (sekitar 2.1 milyar). Akibatnya signed integer overflow adalah undefined behavior di C++ — compiler boleh menghapus kode yang mengandalkannya. Untuk input kompetitif yang sering menyentuh 10^9, kumulatif sum bisa melebihi batas ini.

2. Off-by-One #

Bug off-by-one muncul ketika batas loop atau perbandingan salah satu posisi. Contoh kanonik: < vs <= pada perbandingan threshold. Hasilnya berbeda 1 elemen — kadang lolos uji sample tetapi salah pada hidden test.

Formula mid = (lo + hi) / 2 dapat overflow bila lo + hi > INT_MAX. Solusi kanonik: mid = lo + (hi - lo) / 2. Bug ini terkenal di industri — pernah menyebabkan Google’s blog post tentang bug binary search yang tersembunyi selama 9 tahun.

Kode: Harness Edge Case Komprehensif #

cpp 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>
#include <functional>

// Binary search: bug klasik overflow pada mid = (lo+hi)/2
int binary_search_bug(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;  // bisa overflow bila lo+hi > INT_MAX
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// Versi aman: mid = lo + (hi - lo) / 2
int binary_search_ok(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

long long sum_array_ok(const std::vector<int>& a) {
    long long s = 0;
    for (int x : a) s += x;
    return s;
}

int sum_array_bug_overflow(const std::vector<int>& a) {
    int s = 0;
    for (int x : a) s += x;  // overflow bila |sum| > 2^31
    return s;
}

int count_less_bug(const std::vector<int>& a, int threshold) {
    int cnt = 0;
    for (int x : a) if (x <= threshold) cnt++;  // BUG: harusnya <
    return cnt;
}
int count_less_ok(const std::vector<int>& a, int threshold) {
    int cnt = 0;
    for (int x : a) if (x < threshold) cnt++;
    return cnt;
}

int main() {
    // Edge 1: array kosong
    std::vector<int> empty = {};
    std::cout << "[Edge: empty] binary_search_ok(empty, 5) = "
              << binary_search_ok(empty, 5) << " (expected -1)\n";

    // Edge 2: single elemen
    std::vector<int> single = {42};
    std::cout << "[Edge: single] binary_search_ok({42}, 42) = "
              << binary_search_ok(single, 42) << " (expected 0)\n";
    std::cout << "[Edge: single] binary_search_ok({42}, 7)  = "
              << binary_search_ok(single, 7)  << " (expected -1)\n";

    // Edge 3: target lebih kecil dari semua
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "[Edge: target < all] binary_search_ok(v, 5) = "
              << binary_search_ok(v, 5) << " (expected -1)\n";

    // Edge 4: target lebih besar dari semua
    std::cout << "[Edge: target > all] binary_search_ok(v, 100) = "
              << binary_search_ok(v, 100) << " (expected -1)\n";

    // Edge 5: target sama dengan elemen pertama dan terakhir
    std::cout << "[Edge: first hit] binary_search_ok(v, 10) = "
              << binary_search_ok(v, 10) << " (expected 0)\n";
    std::cout << "[Edge: last hit]  binary_search_ok(v, 50) = "
              << binary_search_ok(v, 50) << " (expected 4)\n";

    // Edge 6: duplikat di tengah
    std::vector<int> dup = {1, 3, 3, 3, 5};
    std::cout << "[Edge: duplicates] binary_search_ok(dup, 3) = "
              << binary_search_ok(dup, 3) << " (expected 1, 2, or 3)\n";

    // Edge 7: overflow integer pada sum
    std::vector<int> big(100000, 100000);
    std::cout << "\n[Edge: overflow] sum_array_bug_overflow(big) = "
              << sum_array_bug_overflow(big) << " (SALAH)\n";
    std::cout << "[Edge: overflow] sum_array_ok(big)            = "
              << sum_array_ok(big) << " (BENAR)\n";

    // Edge 8: off-by-one
    std::vector<int> thr = {1, 2, 3, 4, 5};
    std::cout << "\n[Edge: off-by-one] count_less_bug(thr, 3) = "
              << count_less_bug(thr, 3) << " (SALAH, seharusnya 2)\n";
    std::cout << "[Edge: off-by-one] count_less_ok(thr, 3)  = "
              << count_less_ok(thr, 3) << " (BENAR)\n";

    return 0;
}

Output yang Dihasilkan:

text 
[Edge: empty] binary_search_ok(empty, 5) = -1 (expected -1)
[Edge: single] binary_search_ok({42}, 42) = 0 (expected 0)
[Edge: single] binary_search_ok({42}, 7)  = -1 (expected -1)
[Edge: target < all] binary_search_ok(v, 5) = -1 (expected -1)
[Edge: target > all] binary_search_ok(v, 100) = -1 (expected -1)
[Edge: first hit] binary_search_ok(v, 10) = 0 (expected 0)
[Edge: last hit]  binary_search_ok(v, 50) = 4 (expected 4)
[Edge: duplicates] binary_search_ok(dup, 3) = 2 (expected 1, 2, or 3)

[Edge: overflow] sum_array_bug_overflow(big) = 1410065408 (SALAH)
[Edge: overflow] sum_array_ok(big)            = 10000000000 (BENAR)

[Edge: off-by-one] count_less_bug(thr, 3) = 3 (SALAH, seharusnya 2)
[Edge: off-by-one] count_less_ok(thr, 3)  = 2 (BENAR)

Bedah Kode Baris-per-Baris #

  1. int mid = (lo + hi) / 2; (bug): penjumlahan lo + hi dilakukan dalam int. Bila lo = 1'500'000'000 dan hi = 2'000'000'000, hasil penjumlahan 3'500'000'000 melebihi INT_MAX ≈ 2'147'483'647 → signed overflow → UB. Biasanya menjadi nilai negatif yang kemudian mengakses a[negatif] → crash.
  2. int mid = lo + (hi - lo) / 2; (aman): hi - lo selalu non-negatif dan tidak overflow selama hi >= lo. Bagi 2 lalu tambahkan ke lo. Hasil identik secara matematis tetapi tanpa overflow.
  3. long long s = 0; for (int x : a) s += x;: tipe long long (64-bit) menampung hingga ±9.2 × 10^18. Untuk big(100000, 100000) = 10^10, aman. Versi int overflow menghasilkan 1'410'065'408 (sisa modular 2^32).
  4. if (x <= threshold) cnt++; (bug): spesifikasi “kurang dari” adalah <, tetapi kode pakai <=. Untuk threshold 3 dan array {1,2,3,4,5}, versi bug menghitung 1,2,3 = 3 elemen, sedangkan versi benar 1,2 = 2 elemen.
  5. Edge case “target > all”: target 100 pada array v = {10,20,30,40,50} — loop berakhir dengan lo > hi setelah mencapai indeks 5. Kembalian -1.
  6. Edge case “duplikat”: untuk target 3 di {1,3,3,3,5}, binary search bisa mengembalikan indeks 1, 2, atau 3 — semuanya valid. Soal sering mensyaratkan indeks pertama/terakhir, yang memerlukan modifikasi setelah hit.

Checklist Edge Case untuk Setiap Algoritma #

PertanyaanEdge Case Terkait
Apa yang terjadi bila koleksi kosong?{}
Apa yang terjadi bila koleksi punya satu elemen?{x}
Apa yang terjadi bila elemen = batas tipe?INT_MAX, INT_MIN
Apa yang terjadi bila semua elemen sama?{x,x,x,x}
Apa yang terjadi bila input sudah terurut?{1,2,3,4,5}
Apa yang terjadi bila input terurut terbalik?{5,4,3,2,1}
Apa yang terjadi bila ada duplikat?{1,3,3,3,5}
Apa yang terjadi bila target tidak ada?target = elemen di luar rentang
Apa yang terjadi bila input maksimum n?n = 10^5 atau n = 10^6

Ringkasan #

  • Delapan kategori edge case wajib: kosong, satu elemen, maksimum/minimum, negatif semua, sorted, reverse sorted, duplikat, target di ujung.
  • Tiga bug klasik: integer overflow (tipe terlalu sempit), off-by-one (< vs <=), mid overflow pada binary search ((lo+hi)/2).
  • mid = lo + (hi - lo) / 2 adalah idiom aman untuk binary search pada rentang besar.
  • Signed overflow adalah undefined behavior — gunakan long long bila rentang nilai mendekati batas int.
  • Harness edge case dapat dipakai ulang lintas algoritma dengan kategori yang sama.