module Binary_searchable_intf:sig
..end
binary_search
function for a sequence, and functors for building
binary_search
functions.binary_search
function for a sequence, and functors for building
binary_search
functions.module type Indexable =sig
..end
Indexable
type is a finite sequence of elements indexed by consecutive integers
0
...
module type Indexable1 =sig
..end
type('t, 'elt)
binary_search =?pos:int ->
?len:int ->
't ->
compare:('elt -> 'elt -> int) ->
[ `First_equal_to
| `First_greater_than_or_equal_to
| `First_strictly_greater_than
| `Last_equal_to
| `Last_less_than_or_equal_to
| `Last_strictly_less_than ] -> 'elt -> int option
type('t, 'elt)
binary_search_segmented =?pos:int ->
?len:int ->
't ->
segment_of:('elt -> [ `Left | `Right ]) ->
[ `First_on_right | `Last_on_left ] -> int option
module type S =sig
..end
module type S1 =sig
..end
module type S1_permissions =sig
..end
module type Binary_searchable =sig
..end
binary_search
function for a sequence, and functors for building
binary_search
functions.Indexable
type is a finite sequence of elements indexed by consecutive integers
0
... length t - 1
. get
and length
must be O(1) for the resulting
binary_search
to be lg(n).Binary_searchable
, we need to be able to
construct t
with two different values small < big
. We also need to be able to
build a t
from an elt array
.| < elt X |
| <= elt X |
| = elt X |
| X = elt |
| X >= elt |
| X > elt |
The functions produced by this functor are very powerful, but also somewhat
complex to read. Here are some simple examples to clarify the use cases.
Below we assume that the function compare
is in scope:
(* find the index of an element [e] in [t] *)
binary_search t ~compare `First_equal_to e;
(* find the index where an element [e] should be inserted *)
binary_search t ~compare `First_greater_than_or_equal_to e;
(* find the index in [t] where all elements to the left are less than [e] *)
binary_search_segmented t ~segment_of:(fun e' ->
if compare e' e <= 0 then `Left else `Right) `First_on_right
binary_search ?pos ?len t ~compare which elt
takes t
that is sorted in
nondecreasing order according to compare
, where compare
and elt
divide t
into three (possibly empty) segments:
| < elt | = elt | > elt |
binary_search
returns the index in t
of an element on the boundary of segments
as specified by which
. See the diagram below next to the which
variants.
By default, binary_search
searches the entire t
. One can supply ?pos
or
?len
to search a slice of t
.
binary_search
does not check that compare
orders t
, and behavior is
unspecified if compare
doesn't order t
. Behavior is also unspecified if
compare
mutates t
.
binary_search_segmented ?pos ?len t ~segment_of which
takes an segment_of
function that divides t
into two (possibly empty) segments:
| segment_of elt = `Left | segment_of elt = `Right |
binary_search_segmented
returns the index of the element on the boundary of the
segments as specified by which
: `Last_on_left
yields the index of the last
element of the left segment, while `First_on_right
yields the index of the first
element of the right segment. It returns None
if the segment is empty.
By default, binary_search
searches the entire t
. One can supply ?pos
or
?len
to search a slice of t
.
binary_search_segmented
does not check that segment_of
segments t
as in the
diagram, and behavior is unspecified if segment_of
doesn't segment t
. Behavior
is also unspecified if segment_of
mutates t
.