Week 92 of 125
TAOCP 6.2.1 Searching an Ordered Table
Sign up or sign in to tick these off and give this week a due date.
-
Binary search and its variants: uniform binary search, Fibonacci search, and interpolation search, with analysis and a careful look at how easy it is to get binary search wrong.
Time About 7 hours this week
Why it matters
Binary search is famously hard to write correctly. Knowing the variants also helps with things like branch-free search and searching on sorted disk pages.
Before you start
- 6.1 Sequential Searching
How to approach it
Write binary search from memory, then test it exhaustively on all arrays up to size 10 and all targets. Implement interpolation search and test it on uniform and skewed data.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Off-by-one in bounds and infinite loops when lo and hi are adjacent.
- Midpoint overflow on very large arrays.