Base.Binary_searchSourceFunctions for performing binary searches over ordered sequences given length and get functions.
These functions can be specialized and added to a data structure using the functors supplied in Binary_searchable and described in Binary_searchable_intf.
Below we assume that the functions get, length and compare are in scope:
(* Find the index of an element [e] in [t] *)
binary_search t ~get ~length ~compare `First_equal_to e;
(* Find the index where an element [e] should be inserted *)
binary_search t ~get ~length ~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
~get
~length
~segment_of:(fun e' -> if compare e' e <= 0 then `Left else `Right)
`First_on_rightval binary_search :
('elt : value_or_null) 'key 't. ?pos:int @ local ->
?len:int @ local ->
't ->
length:('t -> int) @ local ->
get:('t -> (int -> 'elt) @ local) @ local ->
compare:('elt -> ('key -> int) @ local) @ local ->
[ `Last_strictly_less_than
| `Last_less_than_or_equal_to
| `Last_equal_to
| `First_equal_to
| `First_greater_than_or_equal_to
| `First_strictly_greater_than ] ->
'key ->
int option @ local @@ portablebinary_search ?pos ?len t ~length ~get ~compare which elt takes t that is sorted in increasing 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.
val binary_search_segmented :
('elt : value_or_null) 't. ?pos:int @ local ->
?len:int @ local ->
't ->
length:('t -> int) @ local ->
get:('t -> (int -> 'elt) @ local) @ local ->
segment_of:('elt -> [ `Left | `Right ]) @ local ->
[ `Last_on_left | `First_on_right ] ->
int option @ local @@ portablebinary_search_segmented ?pos ?len t ~length ~get ~segment_of which takes a 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_segmented 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.