Documentation

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))$

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

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.

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.