Interpolation Search Algorithm

Interpolation search is an advanced searching algorithm that is designed for sorted and uniformly distributed datasets. Unlike the Binary search algorithm, which always checks the middle element, this search algorithm estimates the probable position of the target value using a mathematical formula, which makes it faster than Binary search in average cases.

In this article, we will discuss what interpolation search is, its formula, algorithm, pseudocode, implementations in C++, Python, and Java, along with its applications, advantages, and limitations.

What is the Interpolation Search?

Interpolation search is an algorithm similar to binary search, which is used for searching for a given target in a sorted array. It is an improved version of Binary search that works on a sorted and uniformly distributed dataset. In binary search, the search range is divided into two equal halves, but this search algorithm estimates the likely position of the target value based on the values at the boundaries of the search interval. Also, for estimating the likely position of the target value, one formula is used. 

Formula for Estimation:

• pos → estimated position of the key
• x →  value we are searching for
• A[low], A[high] → values at the search boundaries

How Interpolation Search Algorithm Works

To understand how interpolation search works, let’s take an example to start with. 

Now, imagine you have a dictionary, and the words in the dictionary are arranged in sorted order, starting with A and ending with Z. All words starting with A or B will be at the beginning, words starting with M or N will be somewhere around the middle, and words starting with Y or Z will be near the end.

Example sequence:

apple, bicycle, ……., tiger, zebra

Now, let’s see how you search for these words in real life.

In real life, what you basically do is, if you want to look up the word “bicycle”, you will instinctively open near the beginning of the dictionary, because you know that’s where all B-words are.

Similarly, if you are searching for “zebra”, you won’t waste time near the middle, and you will jump directly to the end because you know that Z words are there.

And, in the same way, if you are searching for “tiger”, you will naturally look around the middle or later middle of the dictionary.

This instinct process, which you have used to search for the words, tells us something important:

• It doesn’t always make sense to start in the middle (like binary search does).
• Instead, we can make a better guess about where the element lies, depending on its value.
• Also, if the data is sorted and uniformly distributed, we can estimate the likely position of the element using a formula, rather than blindly splitting the array into two halves every time.

From this example, we can easily conclude the Principle of Interpolation Search.

Interpolation Search is built on this human instinct:

• In a uniformly distributed dataset or sorted array, the position of an element can be predicted proportionally.
• By “interpolating” the position of the element, the algorithm jumps closer to the target value instead of always checking the middle.

This is why Interpolation Search is often faster than Binary Search on uniform data.

Kickstart Your Software Development Career.

Enroll Now - Start Your Journey Today!

Explore Program

Derivation of Interpolation Search Formula

At first, we assume that the elements in the array are linearly distributed (uniform distribution).

So, we can model the relationship between the index (x-axis) and the array values (y-axis) with the equation of a straight line:

y = m * x + c

Here:

• y = value in the array
• x = index of that value
• m = slope of the line
• c = intercept

Now, 

• At index high, value is arr[high]:

arr[high] = m * high + c          ……………(1)

• At index low, value is arr[low]:

arr[low] = m * low + c            ……………(2)

• At index pos (where we expect x to be):

x = m * pos + c                     ……………(3)

Next, we have to find the Slope (m).

For this, subtract equation (2) from equation (1):

(arr[high] - arr[low]) = m * (high - low)

So, it will become

m = (arr[high] - arr[low]) / (high - low)

As a next step, we have to eliminate c.

So, for eliminating c, subtract equation (2) from equation (3):

x - arr[low] = m * (pos - low)        …………(4)

Now, solve the equation (4) for pos:

pos = low + [(x - arr[low])] / m​

Substitute the value of m:

pos = low + ((x - arr[low]) * (high - low)) / (arr[high] - arr[low])

Finally, this is the interpolation search position formula we use in the algorithm.

Algorithm for Interpolation Search

Here is a clear step-by-step algorithm for interpolation search.

Some preconditions are:

• Array A is sorted in nondecreasing (ascending) order.
• And, we are searching for key x.

Steps:

1. Initialize the boundaries to start with.
   Set low = 0, high = n – 1.
   
2. Now, exit early if the value is out of range.
   If x < A[low] or x > A[high], which means that the key isn’t present, and you have to stop (not found).
   
3. Handle a degenerate segment
   If A[low] == A[high]:
   • If x == A[low], found at low.
   • Else, stop (not found).
     (Prevents division by zero in the next step.)
     
4. Estimate the likely position (interpolation)
   Compute the position,
   pos = low + ((x – arr[low]) * (high – low)) / (arr[high] – arr[low])​ (If indices must be integers, round/floor to the nearest valid index within [low, high].)
5. Compare and narrow the search
   • If A[pos] == x: found at pos.
   • If A[pos] < x: move right → set low = pos + 1.
   • If A[pos] > x: move left → set high = pos − 1.
     
6. Repeat
   Go back to Step 2 (with the updated low, high) until low is greater than high or you return “found.”
   
7. Not found condition
   If the loop ends without a match, report not found.

A mini walk-through for better understanding:

Array: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Search: x = 70

• low=0, high=8, x in range [10, 90] 
• pos = 0 + ((70-10)*(8-0))/(90-10) = (60*8)/80 = 6
• Compare A[6] = 70 → found.

Pseudocode for Interpolation Search

Here is the clear and step-by-step pseudocode for Interpolation Search.

INTERPOLATION_SEARCH(A, n, x)
    Input: A → sorted array of size n
           x → value to search
    Output: index of x if found, otherwise -1

    low ← 0
    high ← n - 1

    WHILE low ≤ high AND x ≥ A[low] AND x ≤ A[high] DO
        // Estimate position using interpolation formula
        pos ← low + ((x - A[low]) * (high - low)) / (A[high] - A[low])

        IF A[pos] = x THEN
            RETURN pos      // Element found
        ELSE IF A[pos] < x THEN
            low ← pos + 1   // Search in the right part
        ELSE
            high ← pos - 1  // Search in the left part
        ENDIF
    ENDWHILE

    RETURN -1   // Element not found

Implementation of Interpolation Search

Here is how you can easily implement interpolation searching in different programming languages such as C++, Python, and Java.

Implementation of Interpolation Search in C++

Output:

The above program uses a function interpolationSearch that searches a sorted array for a value x using the interpolation formula. It starts with the range [lo, hi] and keeps estimating the possible index (pos) of the element rather than always picking the middle. If arr[pos] equals x, the program returns pos; otherwise, it keeps reducing the range more to the left or right. The main function generates an array, searches for 70, then shows the output (either the index or “not found”).

Python Implementation of Interpolation Search

Output:

The Python program above demonstrates the Interpolation Search on a sorted array. It determines the probable index of the target to be searched in a sorted array using a formula, rather than implementing the traditional searching logic of checking the middle index in all steps. At every step, the algorithm checks the feasible range, i.e., if the search element is greater than the left bound of the range, it moves towards the right range; else it moves left till the data element is found or till the feasible range becomes invalid. It prints the index after the element is found, else prints “not found.”

Implementation of Interpolation Search in Java

Output:

In the Java program, we have defined an interpolationSearch method. This method searches for a key x in a sorted array by calculating an estimated index pos using the interpolation formula. This formula relies on the values at low and high (lo and hi) values; if the value at arr[pos] equals the key we are searching for, we return pos; if not, we adjust the search window by moving left or right depending on the sign of the result. The main method of the Java program demonstrates the algorithm by searching for 70 and printing whether it was found.

Complexity Analysis of Interpolation Search

Here is the table that shows the time and space complexity of Interpolation Search.

Now, let’s understand the complexity analysis for different cases in more depth.

Time Complexity of Interpolation Search

Here is the time complexity analysis of this searching algorithm.

Best Case:

• O(1) → The element is found on the first space exploration (e.g., searching the boundary values).

Average Case (uniform distribution):

• O(log log n) → Much faster than Binary Search (O(log n)), because the interpolation formula gives the output that lands close to the target.

Worst Case (non-uniform/skewed distribution):

• O(n) → If data is highly uneven (e.g., exponential gaps between values), then the interpolation guesses poorly and reduces only one element at a time.

Space Complexity of Interpolation Search

Here is the analysis of the space complexity of Interpolation Search.

The space complexity of Interpolation Search is O(1). This is because the algorithm only requires a few extra variables (low, high, pos) to keep track of the search range and the estimated position, regardless of the input array size. No additional data structures or recursive calls are used, so the memory consumption stays constant.

Applications of Interpolation Search

1. Searching in Sorted Numeric Datasets: This searching algorithm works well with data such as student roll numbers, employee IDs, or sequential records.
2. Contact Lists of SmartPhones: The Interpolation search algorithm efficiently locates entries when numbers or names are uniformly distributed in your smartphone.
3. Indexing of Database: It is also used for searching keys in large sorted files or index blocks with uniform key distribution.
4. Library Systems: This algorithm also helps in searching books/journals by accession numbers (often sequential and uniformly spread).
5. File Systems: It is used in cases where records are stored in sorted order and a quick search is needed.

Binary Search vs Interpolation Search

Here is the table that shows the difference between Binary Search and Interpolation Search.

Get Certified in Software Engineering and Boost Your Career!

Enroll for Online Certification Now!

Explore Program

Benefits of Interpolation Search

• Faster: This algorithm is faster than Binary Search on large and uniformly distributed datasets.
• Reliable: It works well for numeric keys such as IDs, roll numbers, phone numbers, etc.
• Space-Efficient: Interpolation search is space-efficient, because it requires only constant extra space (O(1)).
• Uses Intuitional Approach: It mimics human intuition for searching in ordered data, like finding words in a dictionary.

Limitations of Interpolation Search

• Needs Uniform Data: It reduces down or its performance becomes O(n) if the data is skewed or uneven.
• Difficult to Implement: It is more difficult to implement compared to Binary Search.
• Needs Sorted Data: This algorithm requires a sorted array or data to work/function correctly.
• Operator Sensitive: It is sensitive to division by zero errors if arr[high] == arr[low].

Conclusion

From the above discussion, we can conclude that Interpolation search is an efficient improvement over Binary Search, which can be used while dealing with sorted and uniformly distributed datasets. Instead of always checking the middle, this algorithm estimates the likely position of the key using a formula, often jumping closer to the target. This makes it faster than Binary Search in average cases (O(log log n)), though it can degrade to O(n) on non-uniform data. It is also space-efficient, intuitive, and useful in applications like databases, contact lists, and numeric record searches. However, its dependency on uniformity and slightly complex implementation limit its general-purpose use compared to Binary Search. So, by understanding its definition, algorithm, pseudocode, implementation in different programming languages, and applications, you can easily use it to solve the problems related to searching.

Useful Resources:

• Searching in Data Structures – Algorithms, and Types
• What is DSA? Understanding Data Structures and Algorithms
• Sorting Algorithms in C++
• What is Selection Sort Algorithm in Data Structures?
• Bucket Sort Algorithm: Pseudocode & Time Complexity

FAQs on Interpolation Search in Data Structures