# Module `Base.Binary_search`

Functions 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`

.

### Examples

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_right
```

`val binary_search : ?pos:int -> ?len:int -> 't -> length:('t -> int) -> get:('t -> int -> 'elt) -> compare:('elt -> 'key -> int) -> [ `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`

`binary_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 : ?pos:int -> ?len:int -> 't -> length:('t -> int) -> get:('t -> int -> 'elt) -> segment_of:('elt -> [ `Left | `Right ]) -> [ `Last_on_left | `First_on_right ] -> int option`

`binary_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`

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`

.