A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A loop invariant is a condition that remains true before, during, and after each iteration. Identifying invariants helps design correct loops. For example, in a summation loop, the invariant might be: sum contains the total of elements seen so far.
Identify the invariant for simple loops; use invariants to prove loop correctness by hand; test the invariant at each iteration with debug prints.
That invariants are optional or academic; that invariants change during the loop (they don't—they're maintained by each iteration); that every loop needs an explicit invariant (mental verification is often sufficient).
You know how to write for loops and while loops that iterate through data, accumulate results, and search for values. But how do you know a loop is *correct*? Not just that it works on one test case, but that it will produce the right answer for every valid input? Loop invariants are the mental tool that answers this question, and learning to think in terms of invariants transforms loop writing from trial-and-error into principled design.
A loop invariant is a statement about your program's variables that is true every time execution reaches the top of the loop — before the first iteration, between every pair of iterations, and after the loop ends. Consider a loop that sums an array: `total = 0; for i in range(len(arr)): total += arr[i]`. The invariant is: "at the start of each iteration, `total` equals the sum of `arr[0]` through `arr[i-1]`." Before the first iteration (i = 0), total is 0, which is the empty sum — the invariant holds. Each iteration adds `arr[i]` to total and increments i, so the invariant is maintained. After the loop ends (i = len(arr)), the invariant tells us total equals the sum of the entire array. This three-step reasoning — initialization, maintenance, and termination — is how invariants prove correctness.
The practical power of invariants is in *designing* loops, not just verifying them after the fact. When you are stuck writing a loop, ask yourself: "What should be true about my variables at each step?" The answer is your invariant, and it tells you what the loop body needs to do. For a binary search, the invariant is: "the target, if it exists, is between indices `low` and `high`." This invariant dictates every decision in the loop — how to compute the midpoint, which half to discard, and when to stop. Without the invariant, binary search is a minefield of off-by-one errors. With the invariant, each line of code has a clear reason.
You do not need to write invariants down formally for every loop. For simple accumulation or counting loops, the invariant is obvious enough to hold in your head. But whenever a loop is tricky — when it manipulates multiple indices, when the termination condition is subtle, or when you have been debugging for more than a few minutes — stop and explicitly state the invariant. Write it as a comment above the loop. If you cannot articulate what should be true at each iteration, you do not yet understand your own loop well enough to trust it. The invariant is not academic overhead; it is the clearest expression of what the loop is actually doing.