40 Algorithms Every Programmer Should Know

Interpolation Search

Binary search is based on the logic that it focuses on the middle section of the data. Interpolation search is more sophisticated. It uses the target value to estimate the position of the element in the sorted array. Let's try to understand it by using an example. Let's assume we want to search for a word in an English dictionary, such as the word river. We will use this information to interpolate and start searching for words starting with r. A more generalized interpolation search can be programmed as follows:

def IntPolsearch(list,x ):         idx0 = 0         idxn = (len(list) - 1)         found = False         while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]:     # Find the mid point          mid = idx0 +int(((float(idxn - idx0)/( list[idxn] ...