wire / wire-format / binary-search

Binary search

Search in a sorted array by repeatedly halving the search space. Compare target with middle element; if equal, found; if less, search left half; if greater, search right half. O(log n) comparisons. Requires sorted array. Variants: lower_bound (first ≥ target), upper_bound (first > target), binary search on answer (monotonic predicate).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Binary search

wire format

spec: Binary search

Search in a sorted array by repeatedly halving the search space. Compare target with middle element; if equal, found; if less, search left half; if greater, search right half. O(log n) comparisons. Requires sorted array. Variants: lower_bound (first ≥ target), upper_bound (first > target), binary search on answer (monotonic predicate).

fieldsizemeaning
ComparisonO(1)Compare target with middle element.
HalvingO(log n) iterationsEach iteration halves the search space.
Lower boundvariantFind first element ≥ target. Returns insertion point.
Upper boundvariantFind first element > target. Returns insertion point.
Binary search on answervariantSearch for the smallest x such that predicate(x) is true. Requires monotonic predicate.

example:

00 00

Binary search (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/binary-search or /wire-format/binary-search.json