-----------------------------------------------------------------------------
-- |
-- 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 p l h
  | l > h = Nothing
  | p h = Just (searchSafeRange p l h)
  | otherwise = Nothing

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