The BSearchFn functor

The BSearchFn functor provides binary search on sorted monomorphic arrays.

Synopsis

functor BSearchFn (A : MONO_ARRAY)

A : MONO_ARRAY

A : MONO_ARRAY: A structure that implements the MONO_ARRAY signature from the SML Basis Library.

structure A : MONO_ARRAY

val bsearch : (('a * A.elem) -> order) -> ('a * A.array) -> (int * A.elem) option

structure A : MONO_ARRAY: The array structure that defines the element and array types.
val bsearch : (('a * A.elem) -> order) -> ('a * A.array) -> (int * A.elem) option: bsearch cmp (key, arr) returns SOME(ix, elem) where A.sub(arr, ix) is elem and cmp(key, elem) returns EQUAL; if no such element is present, then NONE is returned. This function uses a binary search over the array, which requires that the elements be arranged in increasing order by the cmp function. Usually, the type of the search key will be A.elem, but the interface allows some computation on the elements, as long as the ordering is respected.