Search [2, 4, 6, 8, 10] for 8: four scan reads against three halving probes. Workload decides the plan.
For the worked walkthrough, continue to the topic article and execution trace.
Stage-by-stage execution walkthrough
This request flow decomposes Scan Once or Sort Once, Then Search into 5 sequential stages so you can trace where latency accumulates, which state transitions are irreversible, and where production failure modes occur.
Stage 1: Read the workload
One lookup on static sorted data favors direct probing. Thousands of lookups repay a sort; frequent inserts push toward trees or hash tables instead. During this transition, the runtime enforces strict state invariants before handing control to the next stage: inputs are validated at the boundary, state mutations are ordered deterministically, and latency/resource costs are bounded so downstream consumers never observe a torn or partially initialized state.
Stage 2: Scan cost
A linear scan reads 2, 4, 6, 8 in order: four reads and O(n) time. No precondition needed beyond the array itself. During this transition, the runtime enforces strict state invariants before handing control to the next stage: inputs are validated at the boundary, state mutations are ordered deterministically, and latency/resource costs are bounded so downstream consumers never observe a torn or partially initialized state.
Stage 3: Halve the range
Binary search keeps a candidate range that always contains the answer, probes the middle, and discards the proven half until one index remains. During this transition, the runtime enforces strict state invariants before handing control to the next stage: inputs are validated at the boundary, state mutations are ordered deterministically, and latency/resource costs are bounded so downstream consumers never observe a torn or partially initialized state.
Stage 4: Mind the boundaries
Duplicates need first-or-last searches, not stops at any match. Missing targets shrink to an empty range; reading past the end is the classic off-by-one failure. During this transition, the runtime enforces strict state invariants before handing control to the next stage: inputs are validated at the boundary, state mutations are ordered deterministically, and latency/resource costs are bounded so downstream consumers never observe a torn or partially initialized state.
Stage 5: Pick the sorter
Merge sort stays stable for records; quicksort scans cache-friendly memory but needs randomization against quadratic pivots. Unordered needs rule hash tables out. During this transition, the runtime enforces strict state invariants before handing control to the next stage: inputs are validated at the boundary, state mutations are ordered deterministically, and latency/resource costs are bounded so downstream consumers never observe a torn or partially initialized state.
Production invariants and failure modes
Sorting once pays only under many lookups; the range invariant, not the midpoint formula, is what makes binary search correct. When debugging or capacity-planning this flow in production, instrument each stage boundary separately (measuring both p50 median and p99.9 tail latency), verify what happens when an intermediate stage times out or drops packets, and ensure retry or fallback paths preserve end-to-end idempotency.