Algorithms.BinarySearch

Documentation

binarySearch :: Integral a => (a -> Bool) -> a -> a -> a

Given a monotonic predicate p, a lower bound l, and an upper bound u, with: p l = False p u = True l < u.

Get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

running time: \(O(\log(u - l))\)

binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r

Given a value \(\varepsilon\), a monotone predicate \(p\), and two values \(l\) and \(u\) with:

• \(p l\) = False
• \(p u\) = True
• \(l < u\)

we find a value \(h\) such that:

• \(p h\) = True
• \(p (h - \varepsilon)\) = False

>>> binarySearchUntil (0.1) (>= 0.5) 0 (1 :: Double)
0.5
>>> binarySearchUntil (0.1) (>= 0.51) 0 (1 :: Double)
0.5625
>>> binarySearchUntil (0.01) (>= 0.51) 0 (1 :: Double)
0.515625

binarySearchSeq :: (a -> Bool) -> Seq a -> Maybe Int

Given a monotonic predicate, Get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

returns Nothing if no element satisfies p

running time: \(O(\log^2 n + T*\log n)\), where \(T\) is the time to execute the predicate.

binarySearchVec :: Vector v a => (a -> Bool) -> v a -> Maybe Int

Given a monotonic predicate, get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

returns Nothing if no element satisfies p

running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.