Up

Module Make_without_tests (T : Binary_searchable_intf.Indexable_without_tests) : S with type t := T.t with type elt := T.elt

Parameters

Signature

type elt
type t

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.

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.