University • Algorithms

Invariant Hunter

Prove progress, test invariants and repair faulty loops.

Round 1/6 Score: 0

Loop invariant

Array and pointers

Select a property to test it at loop boundaries.

Proof picture

Initialise Property holds Maintain One iteration Terminate Use property

Prove a property initially, maintain it across the loop and use it at termination.

Investigate correctness

Variant value versus iteration

Search interval

The idea

A loop invariant must hold before and after every iteration. A termination variant is a non-negative integer that strictly decreases while the loop continues. Correct binary search must shrink its interval; an incorrect bound update may leave the interval unchanged.

Proof complete!