Last True Binary Search
Find the last position where a monotone predicate remains true.
Tag
Monotone-Predicate
5 notes
Monotone Predicate Search
Find the boundary where a Boolean predicate changes value over an ordered domain.
Powers of Two Search
Search for a boundary by trying decreasing jumps whose lengths are powers of two.
Binary Search on Answer
Find an optimal value by binary searching a monotone feasibility condition.
First True Binary Search
Find the first position where a monotone predicate becomes true.