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.Bounded

Description

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

Synopsis

- search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a
- searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a
- searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a

# Documentation

search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a Source #

O(log(abs n)). Search a bounded integral type.

If `p` is an upward-closed predicate, `search p` returns `Just n` if and only if `n` is the least such satisfying `p`.

searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a Source #

O(log(abs n)). Search the part of a bounded integral type from a given point.

If `p` is an upward-closed predicate, `searchFrom p l` returns `Just n` if and only if `n` is the least `n >= l` satisfying `p`.

searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a Source #

O(log(abs n)). Search the part of a bounded integral type up to a given point.

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