Search the sorted array [2, 4, 6, 8, 10] for target 8. The array is already sorted, nothing will be inserted, and the answer needs an index, so binary search applies. An unsorted collection could not use it.
1. Check ordering and update needs
The input is sorted and static, which is exactly the precondition binary search needs. If inserts arrived often, a sorted array would shift on every insert and a tree would fit better; if order never mattered, a hash table would answer faster.
2. Choose a search or sort plan
A linear scan reads 2, 4, 6, 8: four reads. Binary search probes midpoints instead. No sorting is needed here because the array arrives sorted; sorting solely for one lookup would cost more than scanning.
3. Narrow or partition the range
Keep the half-open range [lo, hi) of candidates, starting [0, 5). Probe mid = 2 (6 < 8), so the answer lies right: [3, 5). Probe mid = 4 (10 > 8), so the answer lies left: [3, 4). Probe mid = 3 (8 == 8): found at index 3. Each step halves the range, and the invariant that the answer stays inside never breaks.
4. Handle duplicates and bounds
Had the array held [8, 8, 8, 8, 8], stopping at any match would return a middle copy. Boundary searches instead keep narrowing to the first or last position. Had the target been 7, the range would shrink to [3, 3), empty, reporting absence without reading past the end.
5. Return the ordered result
Index 3 in 3 probes against 4 scan reads; the gap widens with size. Sorting the array once with merge sort keeps equal keys stable, while quicksort usually runs faster but needs randomization against quadratic pivots. For the full strategy guide, continue with Searching and Sorting.
Hardware, runtime, and observability notes
When tracing Trace Finding 8 by Scan and by Binary Search in a live production environment (subsystem: execution, primary layer: runtime), keep the following step-level cost model and diagnostic checklist in mind:
- Step 1 (runtime): Check ordering and update needs — verifies state invariants before advancing the execution pointer.
- Step 2 (runtime): Choose a search or sort plan — verifies state invariants before advancing the execution pointer.
- Step 3 (runtime): Narrow or partition the range — verifies state invariants before advancing the execution pointer.
- Step 4 (runtime): Handle duplicates and bounds — verifies state invariants before advancing the execution pointer.
- Step 5 (runtime): Return the ordered result — verifies state invariants before advancing the execution pointer.
Every transition across the runtime boundary carries both a direct CPU/memory cost (cache-line fills, descriptor lookups, lock acquisitions, or context switches) and a tail-latency queueing risk under contention. To verify this trace on your own service, capture latency histograms and hardware/kernel counters across each step boundary, compare cold-cache versus warm-cache execution paths, and confirm that error or timeout branches release all acquired descriptors, locks, and buffers cleanly.