Section 4.3 Studying and working with LLMs

Review code with contracts and tests

When an assistant proposes a fix, separate the specification, the change and the observation. For a function that returns the first position of a value in a sorted array, specify what happens with absent values and duplicates. A trace can work for the first example while the loop fails on an empty array.

Design tests that distinguish implementations

On [1, 4, 4, 4, 9] with target 4, the result should be index 1. A procedure that returns on the first match it sees may return index 2, even though it runs quickly. Include an absent value between two elements, boundary indices and an empty input. On generated cases, compare the implementation with linear search, which is slower and easier to inspect. Both implementations must receive the same inputs.

Empty, missing and duplicate cases feed both a linear search and a binary search. Their outputs are compared.
Figure 4.3. A simple, independent oracle detects divergences without assuming the assistant’s suggestion is correct.

Prove the invariant after testing

When indices range over [lo, hi), a version searching for the first possible position maintains that all elements strictly before lo are smaller than the target. To the right of the boundary, values are greater than or equal to it. At each iteration hi − lo shrinks. After finding the boundary, check equality and bounds before returning a position.