binary-search-2.0.0: Binary and exponential searches

Copyright | (c) Ross Paterson 2008
License | BSD-style
Maintainer | ross@soi.city.ac.uk
Stability | experimental
Portability | portable
Safe Haskell | Safe-Inferred
Language | Haskell2010

Numeric.Search.Integer

Contents

- One-dimensional searches
- Two-dimensional searches

Description

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

Synopsis

- search :: (Integer -> Bool) -> Integer
- searchFrom :: (Integer -> Bool) -> Integer -> Integer
- searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer
- search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)]

# One-dimensional searches

search :: (Integer -> Bool) -> Integer Source #

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 -> Integer Source #

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 Integer Source #

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