Verifying a Binary-Search Probe Sequence in Linear Time

Checking whether a claimed list of probes is the exact sequence a binary search would make costs only Θ(n) — replay the deterministic search and compare, never re-sort or re-search.