Safe Haskell	Safe-Inferred
Language	Haskell2010

BinSearch

Description

Binary search

Sources:

https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure_for_finding_the_leftmost_element

The complexities below assume the predicate takes O(1) time, they should be scaled appropriately if not so.

Synopsis

binSearch :: Integral i => (i -> Bool) -> i -> i -> i
binSearchA :: (a -> Bool) -> Array Int a -> Int
binSearchM :: (Monad m, Integral i) => (i -> m Bool) -> i -> i -> m i

Documentation

binSearch :: Integral i => (i -> Bool) -> i -> i -> i Source #

Returns the first value in [l..h] which satisfies the predicate f, h + 1 otherwise. Returns l if l > h. l + h should not overflow. O(log (h - l + 1)).

binSearchA :: (a -> Bool) -> Array Int a -> Int Source #

binSearch on an Array. O(log n).

binSearchM :: (Monad m, Integral i) => (i -> m Bool) -> i -> i -> m i Source #

binSearch but the predicate returns a monad. O(log (h - l + 1)).