Monotone Predicate Search
Monotone Predicate Search Monotone predicate search finds the transition point of a Boolean predicate over an ordered domain. It is the abstract form behind lower bound, upper bound, first true search, last true search, and binary search on answer. A predicate is monotone if its values change at most once. For first true search, the shape is: $$ false, false, false, true, true, true $$ For last true search, the...