Introduction:
Interpolation search is an improvement to binary search. This will help to achieve better time complexity.
Explanation:
As we have seen in the binary search chapter, we always take the middle index and based on it, we shift towards left or right. But what if we have an option or a formula to approximate the position of the key element?
This can be done with the help of interpolation search.
In interpolation search we use below formula to get the approximate position that is near to the key:
pos = low + ((key – arr[low]) * (high – low)) / (arr[high] – arr[low])
Interpolation search will work if the elements are linearly placed.
Let us understand with the help of an example:
Consider the array:
arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
and the search key = 7;
Pass 0:
Initally all the elements will have below values:
low = 0
high = 7
arr[low] = 1
arr[high] = 8
with the help of above values we try to find an optimal position by using the above formula, we get the position as 6.
AS arr[pos] = 7, which is the search key, we get the output.
Solution in C++
#include<iostream> #include <vector> using namespace std; void interpolation_search( int arr[] , int len, int key) { int low = 0; int high = len -1; int pos; while (low < high) { pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]); if (arr[pos] == key) { cout<<"The element is present"<<endl; return ; } if (key > arr[pos]) low = pos + 1; else high = pos-1; } cout<<"The element is NOT present"<<cout<<endl; return ; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; int len = 8; int key = 7; interpolation_search(arr, len, key); return 0; }
Output:
The element is present
Interpolation search will work on sorted array elements.
The time complexity of the algorithm will be O(log log N) at worst case.