tag

#monotone-predicate

5 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

First True Binary Search

First True Binary Search First true binary search finds the first index where a monotone Boolean predicate becomes true. It generalizes lower bound from array values to any ordered search space. The predicate must have the form: $$ false, false, false, true, true, true $$ Once the predicate becomes true, it must remain true. Problem Given indices from $0$ to $n - 1$ and a predicate $P(i)$, find the smallest...
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Last True Binary Search

Last True Binary Search Last true binary search finds the last index where a monotone Boolean predicate is true. It is the mirror form of first true binary search. The predicate must have the form: $$ true, true, true, false, false, false $$ Once the predicate becomes false, it must remain false. Problem Given indices from $0$ to $n - 1$ and a predicate $P(i)$, find the largest index $i$...
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

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...
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Binary Search on Answer

Binary Search on Answer Binary search on answer finds an optimal numeric value by searching over possible answers instead of searching over array indices. It is used when a direct formula is difficult, but a candidate answer can be tested efficiently. The method requires a monotone feasibility condition. For minimization problems, the predicate often has the form: $$ false, false, false, true, true, true $$ For maximization problems, it often...
algorithms searching binary-search optimization monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Powers of Two Search

Powers of Two Search Powers of two search finds a boundary in a monotone predicate by building the answer from large jumps to small jumps. It is a binary search variant written as controlled forward movement. Instead of maintaining an interval, the algorithm keeps a current position and tries jumps of size: $$ 2^k, 2^{k-1}, \dots, 2^1, 2^0 $$ This style is common in Fenwick trees, binary lifting, implicit arrays,...
algorithms searching binary-search monotone-predicate