๐ Binary Search
This note reconstructs the logic behind binary search from first principles, showing why midpoint comparison is the optimal strategy for reducing search space in a sorted list.
๐ง Step-by-Step Derivation
- Goal: We want to reduce the search space during searching.
- Requirement: To reduce the space, we must know which side of the current number to discard.
- Implication: This requires the list to be sorted, so comparisons are meaningful.
- Setup: With a sorted list, we can compare a chosen number and eliminate either the left or right side.
- Question: Which number should we choose for comparison?
- Observation: If we choose any arbitrary number, one side may contain more elements than the other.
- Average Case: Over many searches, the imbalance averages out โ any position behaves like the middle.
- Best vs Worst Case:
- Choosing a number far from the middle improves the best case (faster if lucky).
- But it worsens the worst case (slower if unlucky).
- Design Principle: We prioritize minimizing the worst case over optimizing the best case.
- Optimal Strategy: Choose the middle element to ensure both sides are equally sized.
- Result: This guarantees that no matter which side the target lies on, the remaining search space is at most half.
- Conclusion: Binary search achieves the best possible worst-case performance while maintaining a solid best case.
๐งฉ Why This Matters
- Binary search builds a balanced decision tree, ensuring logarithmic depth.
- Off-center comparisons risk unbalanced partitions, increasing worst-case depth.
- In systems design, we favor predictable bounds and worst-case minimization over rare best-case wins.
๐ง Summary
Binary search is optimal because it guarantees that the remaining search space is never larger than half, minimizing worst-case depth while maintaining reasonable best-case performance.
Last updated on