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

Description

Binary search of a bounded interval of an integral type for the boundary of an upward-closed set, using a combination of exponential and binary search.

Synopsis

- searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a

# Documentation

searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a Source #

O(log(h-l)). Search a bounded interval of some integral type.

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

For example, the following function determines the first index (if any) at which a value occurs in an ordered array:

    searchArray :: Ord a => a -> Array Int a -> Maybe Int
    searchArray x array = do
      let (lo, hi) = bounds array
      k <- searchFromTo (\ i -> array!i >= x) lo hi
      guard (array!k == x)
      return k