binarySearch

Usage

binarySearch(s, f, a, b)

Signature

binarySearch:

(S, R $\to$ S, R, R) $\to$ (Boolean, R)

Parameter	Type	Description
s	S	The value to search for
f	R $\to$ S	A monotonic increasing function
a	R	The left end of the interval to search
b	R	The right end of the interval to search

Returns

Returns (found?, r) such that $s = f(r)$ if found? is true. Otherwise, found? is false and:

•  if $r < a$ then $s < f(a)$ or $b < a$;
•  if $r \ge b$ then $s > f(b)$;
•  if $a \le r < b$, then $f(r) < s < f(r+1)$;