binary-search-0.1: Binary and exponential searches

Safe HaskellSafe-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 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