1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
-----------------------------------------------------------------------------
-- |
-- 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
|
