Binary search locates a target or insertion position by repeatedly inspecting the middle of an ordered range and discarding the half that cannot contain the target. It works naturally on a sorted list, where each comparison determines whether to continue before or after the current position. section 4.4.2
Use binary search when the data is ordered, but account for the cost of maintaining that order:
- Looking up an entry in a sorted array takes O(log(n)) time and requires no extra memory. section 4.4.2
- Creating the sorted structure costs O(n*log(n)), while adding or removing an entry costs O(n) because elements may need to shift. section 2.3 section 4.4.2
- A sorted list can suit infrequent updates and small datasets, but millions or billions of elements make repeated movement problematic. section 2.3
Searching a phone book
To find Bloom, open near the middle, compare the first surname with Bloom, and discard the region on the wrong side. Repeating this narrows the search between known lower and upper bounds. Sorting contacts first enables the same approach, but maintaining the sorted list makes additions expensive. section 4.4.2
Table 4.2 Using sorted arrays as dictionaries (view table figure)
Compare construction, lookup, insertion, and removal costs for sorted arrays used as dictionaries. section 4.4.2
The method is straightforward in one dimension: each value has an unambiguous left and right side. In higher-dimensional spaces, partitioning is harder because a simple vertical split can ignore other coordinates and separate nearby points poorly. section 8.4.1 section 8.4.2
