Portability | portable |
---|---|
Stability | experimental |
Maintainer | ross@soi.city.ac.uk |
Safe Haskell | Safe-Inferred |
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.
- searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a
Documentation
searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe aSource
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