Binary search locates a target in a sorted sequence by comparing it with the middle element and discarding the half that cannot contain the target. section 6.1.3
Searching a 100-element list
To find target z in [x1, ..., x100], compare z with x50. If z is smaller, continue among the first 50 elements; otherwise, continue among the last 50. Repeat until z is found, or terminate when a comparison is equal. section 6.1.3
Viewed through information theory, choosing the middle location is optimal when every possible target location is equally likely: it minimizes expected posterior entropy after the comparison. section 6.1 section 6.1.3
Figure 6.5 An illustration of binary search on a 100-element list. At each iteration of the search, the target is compared against the middle element of the current list. Depending on the result of this comparison, we remove either the first or second half of the list from the search space.
Trace how each middle-element comparison removes one half of the remaining search space. section 6.1.3
The method supports these information-theoretic ideas:
- Uses sortedness to convert one comparison into a decision about an entire half of the search interval. section 6.1.3
- Connects optimal search decisions with entropy reduction and later motivates information-theoretic policies for optimization. section 6.1
- Extends naturally to a variant where prior information influences each search decision. section 6.3
