In this article, we will construct an interpolation search on an array of integers. In other words, we will learn how to find a given element in a sorted array using the interpolation search. In a binary search, we always find the middle element and compare that with the given one. Depending upon the comparison result, we return the index (if the item is found) or discard the left or right half of the remaining search space.

What is an Interpolation Search on an Array?

The interpolation search is an extension of the binary search, i.e., there is no restriction on choosing the middle element to divide the search space. It selects an index according to the given value to be searched. The notion behind the interpolation search is to choose an index such that the value at that index is closer to the given one. So, if the value to be searched lies at the end of the array or near it, then the index selected will be a high value. However, if the given value is near the starting of the array, then the location taken will be a low value.

The formula to find the index is given as:

Where,

To learn how we got the above formula, consider a linear function, y=f(x), where x is an independent variable and y is the dependent one.

For the sake of this problem, let’s say x represents the index and y is the value at that index. Now, let’s consider two points, x₁ and x₂. Function values at these points are y₁ and y₂, respectively.

Suppose we want to find x for a given y value, i.e., the index of an element. Moreover, we assume that x lies somewhere between x₁ and x₂. Consider the following figure.

For the equation of a line, the two-point formula is:

Since we have to find x, then,

If we take x₁ as the low value and x₂ as the high one, then y₁ will be equal to arr[low], and y₂ will be arr[high]. Also, since y is the value whose index is to be found, it will be equal to key. After we Substitute these values in the above equation, we get:

As you can see, this is the same equation as equation 1.

Implementation of Interpolation Search on an Array of Integers

Let’s now go ahead and implement it. The code is given below.

def interpolationSearch(arr, key, low, high):

  if (low<=high and key >= arr[low] and key <= arr[high]): # x>=x1 and x<=x2
    index = low + (key-arr[low])*(high-low)//(arr[high]-arr[low]) #find index for interpolation search
    #given value is found
    if arr[index] == key:
      return index

    #move the search space to the right of index or discarding the left search space
    elif key > arr[index]:
      return interpolationSearch(arr, key, index+1, high)

    #key is less than arr[index], move the search space to the left of index
    else: 
      return interpolationSearch(arr, key, low, index-1)
  else:
    return -1


arr = [4, 6, 7, 10, 12, 13, 14, 15]
key = 12
position = interpolationSearch(arr, key, 0, len(arr)-1)
if position == -1:
  print(f"Sorry, element {key} is not found")
else:
  print(f"Element {key} is found at index {position}")

Output

Element 12 is found at index 4