monotone predicate
A yes-or-no test over ordered values that is False up to some point and True from then on, never switching back.
In more detail
Because its answers form one block of False followed by one block of True, binary search can find the switch point in O(log n) tests. This lets you binary-search an answer space, such as "the smallest capacity that fits all jobs", not just a list.
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.
- predicate — A function or condition that answers true or false about a value, used to filter, search or check data.
Taught in
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers