Debugging and Test Design

Boundary tests, empty/single-element input, duplicates, sorted/reverse-sorted data, negative values, maximum values, disconnected graphs, cycles, overflow, randomized testing, brute-force comparison, and stress tests.

The program below has a deliberately buggy “first occurrence” binary search. A stress test finds a failing input, then shrinks it automatically until removing any single element would make the test pass.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The shrunken case points straight at the bug: with duplicates, the search stops at the middle occurrence instead of continuing left. The fix is the lowerBound loop of Module 17. A checklist for test design:

empty, one element, two elements, maximum size negatives, zero, maximum values (overflow), duplicates, all equal sorted, reverse sorted, alternating disconnected graph, self-loop, parallel edges, cycle, a path-shaped tree (deep recursion) many small random cases against a brute-force oracle with a fixed seed

#include <bits/stdc++.h>
using namespace std;

int buggyFirst(const vector<int>& a, int x) {          // BUG: returns *some* occurrence, not the first
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}
int bruteFirst(const vector<int>& a, int x) { for (int i = 0; i < (int)a.size(); ++i) if (a[i] == x) return i; return -1; }
bool fails(const vector<int>& a, int x) { return buggyFirst(a, x) != bruteFirst(a, x); }

int main() {
    mt19937 rng(1);
    vector<int> bad; int badX = 0;
    for (int t = 1; t <= 100000 && bad.empty(); ++t) {
        vector<int> a(rng() % 12 + 1); for (int& v : a) v = rng() % 5; sort(a.begin(), a.end());
        int x = rng() % 5;
        if (fails(a, x)) { bad = a; badX = x; cout << "failure found on test " << t << " with " << a.size() << " elements\n"; }
    }
    // shrink: repeatedly try deleting one element while the failure persists
    bool changed = true;
    while (changed) {
        changed = false;
        for (size_t i = 0; i < bad.size(); ++i) {
            vector<int> smaller = ba
…

failure found on test 2 with 8 elements
minimal failing input: a = {1, 1, 2, 3, 3, 4}, x = 3 -> buggy 4, expected 3

Quiz

? What does shrinking a failing test achieve?
+ It reduces the input to a minimal case that still fails, which usually makes the bug obvious :: The run reduced it to a tiny array.
- It makes the test pass :: It keeps it failing.
- It speeds up the program :: No.
- It hides the bug :: The opposite.

? Why compare against a brute-force solution rather than hand-written expected outputs?
+ The brute force covers thousands of random inputs automatically :: Hand-written cases cover only what you thought of.
- Brute force is faster :: It is slower.
- Hand-written tests are never useful :: They are, for edge cases.
- It is required by compilers :: No.

? Which inputs belong in a graph test suite? (select all that apply)
+ A disconnected graph :: Traversals must start from every vertex.
+ Parallel edges and self-loops :: Bridges and cycles.
+ A long path :: Deep recursion.
- Only complete graphs :: Too narrow.