File MonotoneSearch.h

↰ Parent directory (ADS/search)

The search of the first place where a monotone predicate becomes true, when no upper bound on that place is known: on the integers, on a sequence of unknown length, and on the integer square root.

Definition (ADS/search/MonotoneSearch.h)

Detailed Description

  • exponentialSearch(): the least i >= lo with p( i ), for a predicate false and then true; the probes lo , lo + 1 , lo + 3 , lo + 7 , … double the distance from lo until p holds, and a binary search between the last two probes finds the place h, in :math:` 2 lceil log_2 ( h - lo + 1 ) rceil + 1 ` evaluations at most, the method B_1 of Bentley and Yao; their methods B_k, which find the bound itself by an unbounded search of the previous level, reach :math:` log_2 h + log_2 log_2 h + dots `, close to the lower bound. The probes never overflow the type of the integers, and the middle of the binary search is computed on the unsigned distance;

  • unboundedSearch(): the first place of a sequence read one item at a time, get( i ) giving no item past its end, at which there is no item or the item satisfies a predicate false and then true on the items; the count of the items before the first one that is not smaller than a value, in a sorted sequence of unknown length, is the classic case;

  • integerSqrt(): :math:` lfloor sqrt n rfloor , the largest r with :math: r^2 le n , by a binary search on [ 0 , 2^{w / 2} ) for w bits, where :math: m^2 le n ` is tested as :math:` m le lfloor n / m rfloor , so that no product overflows; w / 2 steps. Newton’s iteration :math: x leftarrow lfloor ( x + lfloor n / x rfloor ) / 2 rfloor ` converges quadratically from a start above the root, in :math:` O( log log n ) ` steps from a start within a constant factor; isPerfectSquare() compares the square of the root with n.

The contracts [see File Contract.h]: exponentialSearch() needs a place up to the largest integer where the predicate holds, a precondition checked when the probes reach it, and checks that p holds at the result and not before it, evaluations made with checkingContract() true [see File Sorted.h]; integerSqrt() checks :math:` r^2 le n < ( r + 1 )^2 `. The functions are defined in MonotoneSearch.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizi Divide-et-impera, Raccolte da compiti scritti

    1. Bentley, A. C.-C. Yao, An almost optimal algorithm for unbounded searching, Information Processing Letters 5(3), 82-87, 1976, doi:10.1016/0020-0190(76)90071-5

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions