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 half but to get as close as possible to the search term. The middle position was calculated for using the following rule:

mid_point = (index_of_first_element + index_of_last_element)/2 

We shall replace this formula with a better one that brings us close to the search term. mid_point will receive the return value of the nearest_mid function.

def nearest_mid...