Up
# Module type S

### Signature

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`

.