3 ms·
This relies on knowledge of the distribution, just querying in the middle of A = [1, 2, 4, 8, 16, ..., 2^(n-1)] is slower than binary search
by darknoon 5mo ago
This relies on knowledge of the distribution, just querying in the middle of
A = [1, 2, 4, 8, 16, ..., 2^(n-1)]
is slower than binary search
- locknitpicker 5mo ago> just querying in the middle It's an interpolation search. You interpolate the values you evaluated by whatever method you'd like. No one forces you to do linear interpolation. You can very easily fit a quadratic polynomial with the last 3 points, for example. Interpolation search seems to have a convergence rate of log log n. That's pretty efficient.