loop invariant

A statement about a loop's variables that is true before the loop starts and stays true after every iteration.

In more detail

For binary search the invariant is "if the target is present, it lies between lo and hi". Checking that each update preserves it, and that the loop ends when the range is empty, proves the code correct. Data structures have invariants too, such as the BST ordering rule or the heap property.

Related terms

Taught in

References