úÎ0ï0portable experimentalross@soi.city.ac.uk 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. KFor example, the following function computes discrete logarithms (base 2): # discreteLog :: Integer -> Integer * discreteLog n = search (\ k -> 2^k <= n)  O(log(n-l)). / Search the integers from a given lower bound. If p is an upward-closed predicate,  searchFrom p l =  (\ i -> i >= l && p i).  If no such n& exists (because no integer satisfies p),   searchFrom p does not terminate.  O(log(h-n)). 0 Search the integers up to a given upper bound. If p is an upward-closed predicate, searchTo p h ==  n  if and only if n is the least number n <= h satisfying p.  O(m log(n\m))/. = Two-dimensional search, using an algorithm due described in  Richard Bird, /Saddleback search: a lesson in algorithm design,  in #Mathematics of Program Construction 2006, % Springer LNCS vol. 4014, pp82-89. If p> is closed upwards in each argument on non-negative integers,   search2 p3 returns the minimal non-negative pairs satisfying p, - listed in order of increasing x-coordinate. m and n3 refer to the smaller and larger dimensions of the $ rectangle containing the boundary.  For example, C search2 (\ x y -> x^2 + y^2 >= 25) == [(0,5),(3,4),(4,3),(5,0)] 'Search a bounded interval of integers. If p is an upward-closed predicate,  E searchIntegerRange p l h = 'search' (\ i -> i >= l && p i || i > h) Cost:  O(log(h-l)) calls to p. Like , but assuming l <= h && p h. portable experimentalross@soi.city.ac.uk O(log(h-l)). 2 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. HFor example, the following function determines the first index (if any) . at which a value occurs in an ordered array: 7 searchArray :: Ord a => a -> Array Int a -> Maybe Int  searchArray x array = do  let (lo, hi) = bounds array 1 k <- searchFromTo (\ i -> array!i >= x) lo hi  guard (array!k == x)  return k Like , but assuming l <= h && p h. portable experimentalross@soi.city.ac.uk 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.  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.  O(log(abs n)). A 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. Like , but assuming l <= h && p h.     binary-search-0.0Numeric.Search.IntegerNumeric.Search.RangeNumeric.Search.Boundedsearch searchFromsearchTosearch2 searchFromTobase Data.MaybeJust search2RectsearchIntegerRangesearchSafeRange searchDownsearchUp