binarySearch

Usage

binarySearch(t, a)

Signature

binarySearch:

(T, %) $\to$ (Boolean, MachineInteger)

Parameter	Type	Description
t	T	the value to search for
a	%	an array

Returns

Returns (found?, i) such that $0 \le i < \char93 a$ and $t = a.i$ if found? is true. Otherwise, found? is false and:

•  if $i < 0$ then $t < a.0$;
•  if $i \ge \char93 a - 1$ then $t > a(\char93 a-1)$;
•  if $0 \le i < \char93 a - 1$, then $a.i < t < a(i+1)$.

The array a must be sorted in increasing order. If a is sorted with respect to a different order, it is still possible to use binary search, but from BinarySearch.

See Also

linearSearch