In a nutshell
Interpolation search improves on binary search when a sorted list's values are evenly spread. Rather than always checking the middle, it estimates where the target ought to be from its value — looking for 95 in a 1–100 list, it probes near the far end, just as you'd open a dictionary near the back for 'water'. On uniformly distributed data that guess is so good it runs in about O(log log n); on lopsided data the guesses go wrong and it can degrade to O(n).