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.