⚙️ Controls
CDF is perfectly linear — interpolation finds answer in 1-2 steps!
Random Uniform Value
—
📊 PMF Shape
📋 CDF Table (rounded)
| k | p(k) | F(k) |
|---|
📈 CDF with Interpolation Guess
Interpolation guess
Binary search (midpoint)
Found
🔎 Search Trace
// Interpolation formula:
guess = low + ⌊(U - F[low-1]) / (F[high] - F[low-1]) × (high - low)⌋
low = 1, high = 16
Click "New Search" to begin
💡 The Interpolation Idea
Instead of always checking the middle (binary search), interpolation search estimates where U should be based on linear interpolation of CDF values. If the CDF is nearly linear, this guess is very accurate!
🎯 Best Case: O(log log K)
For uniform distributions, the CDF is perfectly linear. Each guess lands very close to the answer, giving O(log log K) comparisons. For K=16, that's ~2 steps!