Demo: catching a subtle bug in generated binary search with tests

Written Explanation

Step 1: the requirement

Write it before anything else:

search(int[] sorted, int target) returns the index of target in an array sorted in ascending order. If target is absent, it returns -1. The array may be empty. If the array contains duplicates, any matching index is acceptable.

Decisions: -1 for absence (Java's own Arrays.binarySearch instead returns a negative number that encodes the insertion point, so our rule is deliberately different), empty array allowed, duplicates not our concern. A sorted input is a precondition: with an unsorted array, binary search gives an undefined result, and the Java documentation says the same for its own method.

Step 2: tests first

Before any draft, write the tests from the requirement (the checklist from lesson 3: boundaries, first, last, missing, one item):

class SearchTest {
    private final int[] four = {1, 3, 5, 7};
    @Test void emptyArray()           { assertEquals(-1, Search.search(new int[]{}, 5)); }
    @Test void oneItemFound()         { assertEquals(0, Search.search(new int[]{7}, 7)); }
    @Test void oneItemNotFound()      { assertEquals(-1, Search.search(new int[]{7}, 3)); }
    @Test void firstItem()            { assertEquals(0, Search.search(four, 1)); }
    @Test void lastItem()             { assertEquals(3, Search.search(four, 7)); }
    @Test void middleItem()           { assertEquals(2, Search.search(four, 5)); }
    @Test void missingBetween()       { assertEquals(-1, Search.search(four, 4)); }
    @Test void missingBelowAndAbove() { assertEquals(-1, Search.search(four, 0));
                                        assertEquals(-1, Search.search(four, 9)); }
}

Every expected value comes from the requirement: in {1, 3, 5, 7} the 7 is at index 3, and 4 is not there.

Step 3: the draft

Now paste the generated code:

public static int search(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

It compiles. Reading it for the idea (pass 1): keep a window [lo, hi], look at the middle, discard the half that cannot contain the target. That matches the requirement. The code even avoids the classic (lo + hi) / 2 overflow.

Step 4: run the tests

Tests run: 8, Failures: 3
SearchTest.firstItem:9 expected: <0> but was: <-1>
SearchTest.lastItem:10 expected: <3> but was: <-1>
SearchTest.oneItemFound:7 expected: <0> but was: <-1>

Five tests pass, so a quick manual try with 5 would have approved the draft.

Step 5: trace by hand

Take the smallest failing case, [7] with target 7:

With one item, lo and hi are both 0. The window still contains one candidate, but lo < hi says "stop" because it treats a window of one item as empty. The loop never looks at it.

Now [1, 3, 5, 7] with target 7, which explains the last item failure:

The 7 at index 3 was the last candidate when the loop quit. Target 1 fails the same way on the way down, while the middle items are found before the window shrinks to one item.

Diagnosis: the window [lo, hi] is inclusive, so lo == hi means one item remains and must be checked. The condition must be lo <= hi.

Step 6: fix and rerun

Change lo < hi to lo <= hi:

Tests run: 8, Failures: 0
BUILD SUCCESS

When lo > hi, the window is empty and -1 is correct. That also covers the empty array: hi starts at -1, so 0 <= -1 is false and the loop never runs.

Step 7: complexity and explanation

Each iteration discards half of the remaining window, so the number of iterations is about log2(n): for 1,000,000 items about 20 (2^20 is just over a million), against up to a million for a linear scan. Binary search is O(log n) time and O(1) extra memory. (This is arithmetic, not a measurement.)

Finally, explain the code in a comment:

// Keep the inclusive window [lo, hi] that could still contain target.
// Check the middle; discard it and the half that cannot contain target.
// lo <= hi: a window with lo == hi still holds one candidate, so it must be checked.

Add your disclosure line (lesson 4) to the README.

Looking back: how the Beginner level fits together

You now have the whole chain. By topic group:

Where does it go next? The course roadmap lists the next level as the Junior Java Backend Engineer, whose stated promise is to build, test, secure, and deploy a real backend with Spring Boot and PostgreSQL. Its first module is titled "Modern Java", and a later module titled "AI-assisted development workflow" applies this module's habits to team work. We describe nothing beyond those titles and the roadmap's summary.