-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Binary and exponential searches -- -- These modules address the problem of finding the boundary of an -- upward-closed set of integers, using a combination of exponential and -- binary searches. Variants are provided for searching within bounded -- and unbounded intervals of both Integer and bounded integral -- types. @package binary-search @version 0.0 -- | Searching unbounded intervals of integers for the boundary of an -- upward-closed set, using a combination of exponential and binary -- search. module Numeric.Search.Integer -- | O(log(abs n)). Search the integers. -- -- If p is an upward-closed predicate, search p returns -- the least n satisfying p. If no such n -- exists, either because no integer satisfies p or all do, -- search p does not terminate. -- -- For example, the following function computes discrete logarithms (base -- 2): -- -- 
--   discreteLog :: Integer -> Integer
--   discreteLog n = search (\ k -> 2^k <= n)
--
search :: (Integer -> Bool) -> Integer -- | O(log(n-l)). Search the integers from a given lower bound. -- -- If p is an upward-closed predicate, searchFrom p l = -- search (\ i -> i >= l && p i). If no such -- n exists (because no integer satisfies p), -- searchFrom p does not terminate. searchFrom :: (Integer -> Bool) -> Integer -> Integer -- | O(log(h-n)). Search the integers up to a given upper bound. -- -- If p is an upward-closed predicate, searchTo p h == -- Just n if and only if n is the least number n -- <= h satisfying p. searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer -- | O(m log(n\m))/. Two-dimensional search, using an algorithm due -- described in -- -- -- -- If p is closed upwards in each argument on non-negative -- integers, search2 p returns the minimal non-negative pairs -- satisfying p, listed in order of increasing x-coordinate. -- -- m and n refer to the smaller and larger dimensions of -- the rectangle containing the boundary. -- -- For example, -- -- 
--   search2 (\ x y -> x^2 + y^2 >= 25)  ==  [(0,5),(3,4),(4,3),(5,0)]
--
search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)] -- | 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 -- | 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 -- | Searching unbounded intervals within bounded integral types for the -- boundary of an upward-closed set, using a combination of exponential -- and binary search. module Numeric.Search.Bounded -- | O(log(abs n)). Search a bounded integral type. -- -- If p is an upward-closed predicate, search p returns -- Just n if and only if n is the least such satisfying -- p. search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a -- | O(log(abs n)). Search the part of a bounded integral type from -- a given point. -- -- If p is an upward-closed predicate, searchFrom p l -- returns Just n if and only if n is the least n -- >= l satisfying p. searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a -- | O(log(abs n)). Search the part of a bounded integral type up to -- a given point. -- -- If p is an upward-closed predicate, searchTo p h -- returns Just n if and only if n is the least n -- <= h satisfying p. searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a