Copyright | (C) Frank Staals |
---|---|
License | see the LICENSE file |
Maintainer | Frank Staals |
Safe Haskell | None |
Language | Haskell2010 |
Algorithms.BinarySearch
Description
Synopsis
- binarySearch :: Integral a => (a -> Bool) -> a -> a -> a
- binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r
- class BinarySearch v where
Documentation
binarySearch :: Integral a => (a -> Bool) -> a -> a -> a Source #
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 Source #
Given a value ε, a monotone predicate p, and two values l and u with:
- pl = False
- pu = True
- l<u
we find a value h such that:
- ph = True
- p(h−ε) = 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
Binary Searching in some data structure
class BinarySearch v where Source #
Methods
binarySearchIn :: (Elem v -> Bool) -> v -> Maybe (Elem v) Source #
Given a monotonic predicate p and a data structure v, find the element v[h] such that that
for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True
returns Nothing if no element satisfies p
running time: O(T∗logn), where T is the time to execute the predicate.
binarySearchIdxIn :: (Elem v -> Bool) -> v -> Maybe (Index v) Source #
Given a monotonic predicate p and a data structure v, find the index h such that that
for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True
returns Nothing if no element satisfies p
running time: O(T∗logn), where T is the time to execute the predicate.
Instances
Vector v a => BinarySearch (v a) Source # | |
BinarySearch (Seq a) Source # | |
BinarySearch (Set a) Source # | |