How does binary search reduce the search space at each step?

Each step looks at exactly one element, the middle of the interval still in play, and uses that single comparison to throw away everything on one side. If the target is smaller than the middle value it cannot sit to the right of it, so the whole upper half goes; if it is larger, the lower half goes. NIST describes the loop that way: narrow to one half, then repeat until the value turns up or the interval empties.

Halving is what buys the running time. A million sorted entries collapse to one in about twenty comparisons. The detail that surfaces in code review is the midpoint. Writing mid = (high + low) / 2 overflows once the indices approach the largest representable integer; mid = low + (high - low) / 2 computes the same value and never overflows.

Checking every element from the start is linear search, correct but O(n), and exactly what binary search avoids. A random probe discards nothing reliably, because it gives no rule for which side to keep. Re-sorting each step would cost more than the entire search.