O(log(abs n)). Search the integers.

If p is an upward-closed predicate, search p returns the least n satisfying p. If no such n exists, either because no integer satisfies p or all do, search p does not terminate.

For example, the following function computes discrete logarithms (base 2):

discreteLog :: Integer -> Integer discreteLog n = search (\ k -> 2^k <= n)

O(log(n-l)). Search the integers from a given lower bound.

If p is an upward-closed predicate, searchFrom p l = search (\ i -> i >= l && p i). If no such n exists (because no integer satisfies p), searchFrom p does not terminate.

O(log(h-n)). Search the integers up to a given upper bound.

If p is an upward-closed predicate, searchTo p h == Just n if and only if n is the least number n <= h satisfying p.

O(m log(n/m)). Two-dimensional search, using an algorithm due described in

• Richard Bird, Saddleback search: a lesson in algorithm design, in Mathematics of Program Construction 2006, Springer LNCS vol. 4014, pp82-89.

If p is closed upwards in each argument on non-negative integers, search2 p returns the minimal non-negative pairs satisfying p, listed in order of increasing x-coordinate.

m and n refer to the smaller and larger dimensions of the rectangle containing the boundary.

For example,

search2 (\ x y -> x^2 + y^2 >= 25) == [(0,5),(3,4),(4,3),(5,0)]