binary-search-0.1: Binary and exponential searches

Safe HaskellSafe-Inferred




Searching unbounded intervals of integers for the boundary of an upward-closed set, using a combination of exponential and binary search.


One-dimensional searches

search :: (Integer -> Bool) -> IntegerSource

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)

searchFrom :: (Integer -> Bool) -> Integer -> IntegerSource

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.

searchTo :: (Integer -> Bool) -> Integer -> Maybe IntegerSource

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.

Two-dimensional searches

search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)]Source

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)]