| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Sequence.Util
Synopsis
- binarySearchSeq :: (a -> Bool) -> Seq a -> Maybe Int
- binarySearchVec :: Vector v a => (a -> Bool) -> v a -> Maybe Int
- splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
- binarySearch :: Integral a => (a -> Bool) -> a -> a -> a
Documentation
binarySearchSeq :: (a -> Bool) -> Seq a -> Maybe Int Source #
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 Source #
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.
splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source #
Partition the seq s given a monotone predicate p into (xs,ys) such that
all elements in xs do *not* satisfy the predicate p all elements in ys do satisfy the predicate p
all elements in s occur in either xs or ys.
running time: \(O(\log^2 n + T*\log n)\), where \(T\) is the time to execute the predicate.
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))\)