Why Halving Works
In Chapter 25, we learned that looking at everything is too slow.
To go faster, we must Ignore data.
If the data is sorted, we can check the middle element. If it is too low, we ignore the entire left half. We cut the universe in half with one operation.
This is Binary Search (O(log N)).
The Cost of Decisions
But ignoring is not free. Every "cut" is a Branch.
A Linear Scan (Array) is a predictable stroll. The CPU prefetches everything.
A Binary Search is a series of erratic jumps. Every step depends on the previous result, so the CPU cannot overlap work or look ahead.
The Branch Predictor struggles. The Prefetcher gives up. Each step costs tens of cycles (often more than the data access itself).
Binary search touches one value per cache line, wasting the other 63 bytes every time.
On modern CPUs, a bad branch can cost more than reading 100 contiguous values. This creates a Crossover Point.
1. N=16 (Small): Linear Scan (~16 cycles) beats Binary Search (~80 cycles). The "Decisions" cost more than the "Walking".
2. N=256 (Large): Binary Search (~160 cycles) crushes Linear Scan (~256 cycles). The "Walking" becomes unbearable.
The Trap of Structure
Binary Search works because the data is Sorted.
But maintaining a sorted array is expensive. Inserting a new item requires shifting everything
(O(N)), which brings us back to the Bandwidth problem.
To get fast Search and fast Insertion, we desperately invent Linked Structures (Trees).
And that is where memory exacts its revenge.
We traded Bandwidth for Latency.
Binary Search saves Bandwidth (we read less). But it increases Latency (we jump more).
Now we need a structure that supports dynamic data. We will build a Tree.
And we will find that order fails when memory gets scattered.
Is Binary Search always faster than Linear Search?
No. As shown in the Lab, for small N (e.g., < 64), Linear Scan wins. The cost of Branch Mispredictions (flushing the pipeline) in Binary Search outweighs the benefit of ignoring data. Linear Scan is "dumb" but extremely easy for the hardware to optimize.