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,
- Low represents the starting position of the search space.
- High represents the last position of the search space.
-
arr[low]
andarr[high]
are the values of the array at indices low and high, respectively. - The key is the given value to be searched.
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, x1 and x2. Function values at these points are y1 and y2, 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 x1 and x2. 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 x1 as the low value and x2 as the high one, then y1 will be equal to arr[low]
, and y2 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