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

Binary Searching in some data structure

class BinarySearch v where

Associated Types

type Index v :: *

type Elem v :: *

Methods

binarySearchIn :: (Elem v -> Bool) -> v -> Maybe (Elem v)

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*\log n)\), where \(T\) is the time to execute the predicate.

binarySearchIdxIn :: (Elem v -> Bool) -> v -> Maybe (Index v)

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*\log n)\), where \(T\) is the time to execute the predicate.

Instances

Vector v a => BinarySearch (v a)

Defined in Algorithms.BinarySearch

Associated Types

type Index (v a)

type Elem (v a)

Methods

binarySearchIn :: (Elem (v a) -> Bool) -> v a -> Maybe (Elem (v a))

binarySearchIdxIn :: (Elem (v a) -> Bool) -> v a -> Maybe (Index (v a))

BinarySearch (Seq a)

Defined in Algorithms.BinarySearch

Associated Types

type Index (Seq a)

type Elem (Seq a)

Methods

binarySearchIn :: (Elem (Seq a) -> Bool) -> Seq a -> Maybe (Elem (Seq a))

binarySearchIdxIn :: (Elem (Seq a) -> Bool) -> Seq a -> Maybe (Index (Seq a))

BinarySearch (Set a)

Defined in Algorithms.BinarySearch

Associated Types

type Index (Set a)

type Elem (Set a)

Methods

binarySearchIn :: (Elem (Set a) -> Bool) -> Set a -> Maybe (Elem (Set a))

binarySearchIdxIn :: (Elem (Set a) -> Bool) -> Set a -> Maybe (Index (Set a))

Searching on a Sequence