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
- In a loop, find the value of the position from the formula calculated above.
- If the element is found at that index, return and exit.
- 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.
- 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; }