An Explanation of Interpolation Search

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search and Linear Search.

This blog post I will focus on the Interpolation Search. I will explain what is the Interpolation Search, how is Interpolation Search associated with Algorithms, try to break down the concept of Interpolation Search step by step and compare to Binary Search. I wanted to spend some more time covering searching algorithms before I move on to sorting algorithms.

What is Interpolation Search?

An Interpolation Search is a type of searching algorithm. An Interpolation Search is an improvement over Binary Search for scenarios where the values in a sorted array are uniformly distributed.

Binary Search goes to the middle element to check. On the other hand, Interpolation Search may go to different locations according to the value of the key being searched. For example, if the value of the key is close to the last element, Interpolation Search is likely to start search toward the end side.

Interpolation Search: Steps on how it works:

Here is an approach is to do an Interpolation Search:

1. In a loop, calculate the value of “pos” using the probe position formula (which is shown above).
2. If there is a match, return the index of the item, and exit.
3. If the item is less than the arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.
4. Repeat until a match is found or the sub-array reduces to zero.

Interpolation Search: An example

Here is an example of writing the Interpolation Search algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameters: array and the value I want to find. The function returns the index of the found value.

What about time complexity? If the elements are uniformly distributed, then O (log log n)). In worst case it can take up to O(n). So for Interpolation Search to work efficiently the array elements/data should be sorted and uniformly distributed.

Overall Interpolation Search is an important concept to understand when it comes to algorithms. Also is important to compare it with other algorithms like Binary Search. Thank you for reading this blog post. Now that I covered searching algorithms, I will go over sorting algorithms in upcoming blog posts.