wire / wire-format / 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).
aka: Binary search
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).
| field | size | meaning |
|---|---|---|
| Comparison | O(1) | Compare target with middle element. |
| Halving | O(log n) iterations | Each iteration halves the search space. |
| Lower bound | variant | Find first element ≥ target. Returns insertion point. |
| Upper bound | variant | Find first element > target. Returns insertion point. |
| Binary search on answer | variant | Search for the smallest x such that predicate(x) is true. Requires monotonic predicate. |
example:
00 00
Binary search (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/binary-search
or /wire-format/binary-search.json