Module Base.Binary_search

General 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_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.