    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Numeric.Search.Range
    -- Copyright   :  (c) Ross Paterson 2008
    -- License     :  BSD-style
    -- Maintainer  :  ross@soi.city.ac.uk
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- 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.
    --
    -----------------------------------------------------------------------------

    module Numeric.Search.Range (searchFromTo) where

    -- | /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
    --
    searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a
    searchFromTo :: forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
    searchFromTo a -> Bool
    p a
    l a
    h
      | a
    l a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    > a
    h = Maybe a
    forall a. Maybe a
    Nothing
      | a -> Bool
    p a
    h = a -> Maybe a
    forall a. a -> Maybe a
    Just ((a -> Bool) -> a -> a -> a
    forall a. Integral a => (a -> Bool) -> a -> a -> a
    searchSafeRange a -> Bool
    p a
    l a
    h)
      | Bool
    otherwise = Maybe a
    forall a. Maybe a
    Nothing

    -- | Like 'searchFromTo', but assuming @l <= h && p h@.
    searchSafeRange :: Integral a => (a -> Bool) -> a -> a -> a
    searchSafeRange :: forall a. Integral a => (a -> Bool) -> a -> a -> a
    searchSafeRange a -> Bool
    p a
    l a
    h
      | a
    l a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    h = a
    l
      | a -> Bool
    p a
    m = (a -> Bool) -> a -> a -> a
    forall a. Integral a => (a -> Bool) -> a -> a -> a
    searchSafeRange a -> Bool
    p a
    l a
    m
      | Bool
    otherwise = (a -> Bool) -> a -> a -> a
    forall a. Integral a => (a -> Bool) -> a -> a -> a
    searchSafeRange a -> Bool
    p (a
    ma -> a -> a
    forall a. Num a => a -> a -> a
    +a
    1) a
    h
      -- Stay within @min 0 l .. max 0 h@ to avoid overflow.
      where m :: a
    m = a
    l a -> a -> a
    forall a. Integral a => a -> a -> a
    `div` a
    2 a -> a -> a
    forall a. Num a => a -> a -> a
    + a
    h a -> a -> a
    forall a. Integral a => a -> a -> a
    `div` a
    2	-- If l < h, then l <= m < h