Base.Binary_search · base v0.14.3

base

Full standard library replacement for OCaml

Version

IN THIS PACKAGE

library base
- module Base
  - module Applicative
    
    module type Applicative_infix
    
    module type Applicative_infix2
    
    module type Applicative_infix3
    
    module type Basic
    
    module type Basic2
    
    module type Basic2_using_map2
    
    module type Basic3
    
    module type Basic3_using_map2
    
    module type Basic_using_map2
    
    module Compose
    
    argument 1-F
    
    module Applicative_infix
    
    argument 2-G
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type Let_syntax
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module type Let_syntax2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module type Let_syntax3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module Make
    
    argument 1-X
    
    module Applicative_infix
    
    module Make2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make2_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make3
    
    argument 1-X
    
    module Applicative_infix
    
    module Make3_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make_let_syntax
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_let_syntax2
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_let_syntax3
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Of_monad
    
    argument 1-M
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Applicative_infix
    
    module Of_monad2
    
    argument 1-M
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Applicative_infix
    
    module Pair
    
    argument 1-F
    
    module Applicative_infix
    
    argument 2-G
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type S
    
    module Applicative_infix
    
    module type S2
    
    module Applicative_infix
    
    module S2_to_S
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module S2_to_S3
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type S3
    
    module Applicative_infix
    
    module S3_to_S2
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module S_to_S2
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
  - module Array
  - module Avltree
  - module Backtrace
    
    module Exn
  - module Binary_search
  - module Binary_searchable
    
    module type Indexable
    
    module type Indexable1
    
    module Make
    
    argument 1-T
    
    module Make1
    
    argument 1-T
    
    module type S
    
    module type S1
  - module Blit
    
    module Make
    
    argument 1-Sequence
    
    module Make1
    
    argument 1-Sequence
    
    module Make1_generic
    
    argument 1-Sequence
    
    module Make_distinct
    
    argument 1-Src
    
    argument 2-Dst
    
    module Make_to_string
    
    argument 1-T
    
    argument 2-To_bytes
    
    module type S
    
    module type S1
    
    module type S1_distinct
    
    module type S_distinct
    
    module type S_to_string
    
    module type Sequence
    
    module type Sequence1
  - module Bool
    
    module Non_short_circuiting
  - module Buffer
    
    module type S
    
    module To_string
    
    module To_string
  - module Bytes
    
    module From_string
    
    module To_string
  - module Char
    
    module Caseless
    
    module O
  - module Comparable
    
    module Infix
    
    argument 1-T
    
    module Inherit
    
    argument 1-C
    
    argument 2-T
    
    module Make
    
    argument 1-T
    
    module Make_using_comparator
    
    argument 1-T
    
    module Poly
    
    argument 1-T
    
    module Polymorphic_compare
    
    argument 1-T
    
    module type S
    
    module Validate
    
    argument 1-T
    
    module Validate_with_zero
    
    argument 1-T
    
    module With_zero
    
    argument 1-T
  - module Comparator
    
    module Derived
    
    argument 1-M
    
    module Derived2
    
    argument 1-M
    
    module Derived_phantom
    
    argument 1-M
    
    module Make
    
    argument 1-M
    
    module Make1
    
    argument 1-M
    
    module Poly
    
    module type S
    
    module type S1
    
    module type S_fc
    
    module S_to_S1
    
    argument 1-S
  - module Comparisons
    
    module type Infix
    
    module type S
  - module Container
    
    module Continue_or_stop
    
    module type Generic
    
    module type Generic_phantom
    
    module Make
    
    argument 1-T
    
    module Make0
    
    argument 1-T
    
    module Elt
    
    module type S0
    
    module type S0_phantom
    
    module type S1
    
    module type S1_phantom
    
    module type S1_phantom_invariant
    
    module type Summable
  - module Continue_or_stop
  - module Either
    
    module First
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type Focused
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Second
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Equal
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Error
    
    module Internal_repr
  - module Exn
  - module Export
  - module Field
  - module Float
    
    module Class
    
    module O
    
    module O_dot
    
    module Parts
    
    module Terse
  - module Floatable
    
    module type S
  - module Fn
  - module Formatter
  - module Hash
    
    module Builtin
    
    module F
    
    argument 1-Hash
    
    module For_tests
    
    module Builtin
    
    module For_tests
    
    module For_tests
    
    module type Full
    
    module Builtin
    
    module For_tests
    
    module type S
    
    module For_tests
  - module Hash_set
    
    module type Accessors
    
    module Creators
    
    argument 1-Elt
    
    module type Creators_generic
    
    module Key
    
    module type S
    
    module M
    
    argument 1-Elt
    
    module type M_of_sexp
    
    module Poly
    
    module type Sexp_of_m
  - module Hashable
    
    module type Hashable
    
    module type Key
  - module Hasher
    
    module type S
    
    module type S1
  - module Hashtbl
    
    module type Accessors
    
    module Creators
    
    argument 1-Key
    
    module type For_deriving
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module Key
    
    module type S
    
    module M
    
    argument 1-K
    
    module type M_of_sexp
    
    module Merge_into_action
    
    module type Multi
    
    module Poly
    
    module type S_poly
    
    module type S_without_submodules
    
    module type Sexp_of_m
  - module Identifiable
    
    module Make
    
    argument 1-M
    
    module Make_using_comparator
    
    argument 1-M
    
    module type S
  - module Indexed_container
    
    module Make
    
    argument 1-T
    
    module type S1
  - module Info
    
    module Internal_repr
    
    module type S
    
    module Internal_repr
  - module Int
    
    module Hex
    
    module type Hexable
    
    module Hex
    
    module type Int_without_module_types
    
    module Hex
    
    module O
    
    module O
    
    module type Operators
    
    module type Operators_unbounded
    
    module type Round
    
    module type S
    
    module Hex
    
    module O
    
    module type S_common
    
    module Hex
    
    module type S_unbounded
    
    module Hex
    
    module O
  - module Int32
    
    module Hex
    
    module O
  - module Int63
    
    module Hex
    
    module O
    
    module Overflow_exn
  - module Int64
    
    module Hex
    
    module O
  - module Int_conversions
    
    module Make
    
    argument 1-I
    
    module Make_hex
    
    argument 1-I
    
    module Hex
  - module Int_math
    
    module Make
    
    argument 1-X
    
    module type Make_arg
    
    module Private
    
    module Pow_overflow_bounds
  - module Intable
    
    module type S
  - module Invariant
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Lazy
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module T_unforcing
  - module Linked_queue
  - module List
    
    module Assoc
    
    module Infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Or_unequal_lengths
  - module Map
    
    module type Accessors1
    
    module type Accessors2
    
    module type Accessors3
    
    module type Accessors3_with_comparator
    
    module type Accessors_generic
    
    module type Compare_m
    
    module Continue_or_stop
    
    module type Creators1
    
    module type Creators2
    
    module type Creators3_with_comparator
    
    module type Creators_and_accessors1
    
    module type Creators_and_accessors2
    
    module type Creators_and_accessors3_with_comparator
    
    module type Creators_and_accessors_generic
    
    module type Creators_generic
    
    module type Equal_m
    
    module Finished_or_unfinished
    
    module type For_deriving
    
    module type Compare_m
    
    module type Equal_m
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module M
    
    argument 1-K
    
    module type M_of_sexp
    
    module Or_duplicate
    
    module Poly
    
    module type S_poly
    
    module type Sexp_of_m
    
    module Symmetric_diff_element
    
    module Using_comparator
    
    module Empty_without_value_restriction
    
    argument 1-K
    
    module Tree
    
    module With_comparator
    
    module With_first_class_module
    
    module Without_comparator
  - module Maybe_bound
  - module Monad
    
    module type Basic
    
    module type Basic2
    
    module type Basic3
    
    module type Basic_indexed
    
    module Ident
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type Infix
    
    module type Infix2
    
    module type Infix3
    
    module type Infix_indexed
    
    module Make
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make2
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make3
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make_indexed
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S_indexed
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S_without_syntax
    
    module Monad_infix
    
    module type Syntax
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax_indexed
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
  - module Nativeint
    
    module Hex
    
    module O
  - module Nothing
  - module Option
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Option_array
  - module Or_error
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Ordered_collection_common
    
    module Private
  - module Ordering
    
    module Export
  - module Poly
  - module Popcount
  - module Pretty_printer
    
    module Register
    
    argument 1-M
    
    module Register_pp
    
    argument 1-M
    
    module type S
  - module Printf
  - module Queue
    
    module type S
  - module Random
    
    module State
  - module Ref
    
    module And_value
  - module Result
    
    module Export
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Sequence
    
    module Expert
    
    module Generator
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Merge_with_duplicates_element
    
    module Monad_infix
    
    module Step
  - module Set
    
    module type Accessors0
    
    module Named
    
    module type Accessors1
    
    module Named
    
    module type Accessors2
    
    module Named
    
    module type Accessors2_with_comparator
    
    module Named
    
    module type Accessors_generic
    
    module Named
    
    module type Compare_m
    
    module type Creators0
    
    module type Creators1
    
    module type Creators2
    
    module type Creators2_with_comparator
    
    module type Creators_and_accessors0
    
    module Named
    
    module type Creators_and_accessors1
    
    module Named
    
    module type Creators_and_accessors2
    
    module Named
    
    module type Creators_and_accessors2_with_comparator
    
    module Named
    
    module type Creators_generic
    
    module type Elt_plain
    
    module type Equal_m
    
    module type For_deriving
    
    module type Compare_m
    
    module type Equal_m
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module M
    
    argument 1-Elt
    
    module type M_of_sexp
    
    module Merge_to_sequence_element
    
    module Named
    
    module Poly
    
    module Named
    
    module type S_poly
    
    module Named
    
    module type Sexp_of_m
    
    module Using_comparator
    
    module Empty_without_value_restriction
    
    argument 1-Elt
    
    module Named
    
    module Tree
    
    module Named
    
    module With_comparator
    
    module With_first_class_module
    
    module Without_comparator
  - module Sexp
    
    module Private
    
    module Raw_grammar
    
    module Atom
    
    module Builtin
  - module Sexpable
    
    module Of_sexpable
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable1
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable2
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable3
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_stringable
    
    argument 1-M
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Sign
  - module Sign_or_nan
  - module Source_code_position
  - module Stack
    
    module type S
  - module Staged
  - module String
    
    module Caseless
    
    module Escaping
    
    module Search_pattern
  - module Stringable
    
    module type S
  - module Sys
  - module type T
    
    module type T
    
    module type T1
    
    module type T2
    
    module type T3
  - module type T1
  - module type T2
  - module type T3
  - module Type_equal
    
    module Composition_preserves_injectivity
    
    argument 1-M1
    
    argument 2-M2
    
    module Id
    
    module Uid
    
    module type Injective
    
    module type Injective2
    
    module Lift
    
    argument 1-X
    
    module Lift2
    
    argument 1-X
    
    module Lift3
    
    argument 1-X
  - module Uchar
  - module Uniform_array
  - module Unit
  - module Validate
    
    module Infix
  - module Variant
  - module With_return
  - module Word_size
library base.base_internalhash_types
- module Base_internalhash_types
library base.caml
- module Caml
library base.md5
- module Md5_lib
library base.shadow_stdlib
- module Shadow_stdlib

Module Base . Binary_search

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.