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
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
- off-by-one error — A bug where a count or index is one too many or one too few, such as looping one step past the end.
- BST property — The rule that keeps a binary search tree searchable: left subtree keys are smaller than the node, right subtree keys are larger.
- heap property — The rule that every parent in a heap is ordered before its children: no larger than them in a min-heap.
Taught in
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers