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

Taught in

References