Quick, what is the fastest way to search a sorted array? Binary search, right? Wrong. There is actually a method called interpolation search , in which, rather than pessimistically looking in the middle of the array, you use a model of the key distribution to predict the location of the key and look there. Here is a simple example: assume you have an array of length 10, which contains a uniform sample of numbers between 0 and 99. Interpolation search works the same way a person would search. If asked to guess the location of 3 you would probably guess the 1st slot,
Read full article from Beating Binary Search - 2010/06 | LinkedIn Data Team
