Python Data Structures and Algorithms

Interpolation search

There is another variant of the binary search algorithm that may closely be said to mimic more, how humans perform search on any list of items. It is still based off trying to make a good guess of where in a sorted list of items, a search item is likely to be found.

Examine the following list of items for example:

To find 120, we know to look at the right hand portion of the list. Our initial treatment of binary search would typically examine the middle element first in order to determine if it matches the search term.

A more human thing would be to pick a middle element in a such a way as to not only split the array in ...