DAA: Interpolation Search Algorithm

Interpolation Search Algorithm

There is no doubt that binary search is a great algorithm with average time complexity of log n. The feature of discarding one half of the array reduces the search operation.

In accordance with binary search, the interpolation search is an enhanced algorithm. In binary search, as the array is sorted, it always goes to the middle element in each iteration. But interpolation works in a different manner; it may go to different indexes for the key being searched.

For example, if the element to be searched is in the start, the interpolation search will start to search elements from the beginning, not from the last or middle.

The position to start searching the element is calculated from the below formula:

position = low + [ (x - array[low])*(high - low) / (array[high] - arr[Low]) ]

Here,

x: The element to be searched

low: Starting index in our array

high: Ending index in our array

Now let us understand how the position is derived:

(Assumption) The elements in the array are linearly distributed.

We will generalize the equation of the straight line in coordinate geometry, i.e.,

                        y = m * x + c

Here y is the value in the array and x is the index of that value.

Now we insert the low, high and x in the equation -

 array[hi] = m * high + c ----(1)
 array[low] = m * low + c ----(2)
 x = m * position + c     ----(3)
 m = (array[high] - array[low] ) / (high - low)
 Subtracting equation (2) from (3)
 x - array[low] = m * (position - low)
 low + (x - array[low]) / m = position 

position = low + (x - array[low])  * (high - low) / (array[high] - array[low])

Algorithm of interpolation search

1. In a loop, find the value of the position from the formula calculated above.
2. If the element is found at that index, return and exit.
3. If the key to be searched is less than array[position], using the above formula find the starting index from which element will be searched. Otherwise, find it in the right half array.
4. Repeat the above step until the key is found.

C++ Code:

 #include <bits/stdc++.h>
 using namespace std;
 // If the x is found in the array return position of x otherwise, -1
 int interpolationSearch(int array[], int n, int x)
 {
     // The low value start from beginning of array and high points to (n-1)th element
     int low = 0, high = (n - 1);
     // Run a loop to find the element in the boundary
     while (low <= high && x >= array[low] && x <= array[high]) {
         if (low == high) {
             if (array[low] == x)
                 return low;
             return -1;
         }
         // Calculate the position from above formula
         int position = low + (((double)(high - low) / (array[high] - array[low])) * (x - array[low]));
         // If key to be searched is found return position
         if (array[position] == x)
             return position;
         // If key is larger, it is in upper part i.e, right subarray
         if (array[position] < x)
             low = position + 1;
         // If key is smaller, it is in the lower part i.e., left subarray
         else
             high = position - 1;
     }
     return -1;
 }
 int main() // Main function to call interpolation search
 {
     int array[] = { 10, 12, 13, 16, 18, 19, 20, 21 };
     int n = sizeof(array) / sizeof(array[0]);
     int x = 16; // Key to be searched
     int index = interpolationSearch(array, n, x);
     // If key was not found it will return -1
     if (index != -1)
         cout << "Key searched is found at index " << index;
     else
         cout << "key not found.";
     return 0;
 } 

C code:

 #include <stdio.h>
 // If the x is found in the array return position of x otherwise, -1
 int interpolationSearch(int array[], int n, int x)
 {
     // The low value start from beginning of array and high points to (n-1)th element
     int low = 0, high = (n - 1);
     // Run a loop to find the element in the boundary
     while (low <= high && x >= array[low] && x <= array[high]) {
         if (low == high) {
             if (array[low] == x)
                 return low;
             return -1;
         }
         // Calculate the position from above formula
         int position = low + (((double)(high - low) / (array[high] - array[low])) * (x - array[low]));
         // If key to be searched is found return position
         if (array[position] == x)
             return position;
         // If key is larger, it is in upper part i.e, right subarray
         if (array[position] < x)
             low = position + 1;
         // If key is smaller, it is in the lower part i.e, left subarray
         else
             high = position - 1;
     }
     return -1;
 }
 int main() // Main function to call interpolation search
 {
     int array[] = { 10, 12, 13, 16, 18, 19, 20, 21 };
     int n = sizeof(array) / sizeof(array[0]);
     int x = 16; // Key to be searched
     int index = interpolationSearch(array, n, x);
     // If key was not found it will return -1
     if (index != -1)
         printf("Key searched is found at index %d", index);
     else
         printf("key not found.");
     return 0;
 }