# Module type Binary_searchable_intf.S

    module type S = sig .. end

    type elt

    type t

Examples

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

    val binary_search : (t, elt)
           Binary_searchable_intf.binary_search

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

    val binary_search_segmented : (t, elt)
           Binary_searchable_intf.binary_search_segmented

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