Here, we are going to discuss Interpolation Search Algorithm in C++. It is valid only for sorted arrays. Interpolation Search is an Improvement over Binary Search.
Interpolation Search will move to different locations based on the value of a key we are searching for. If the value of a key is near to the last element, Interpolation Search Algorithm starts searching from the end. To find the position, It uses the following formula
pos = s+[(x-arr[s])*(e-s)/(arr[e]-arr[s])
where arr is the input array, x is the element to be searched, starting index of an array is s and the last index is e. If the elements are uniformly distributed, the interpolation search algorithm's complexity can go up to O(log(log n)). In the worst case, it can go up to O(n).
How Code Works:
I passed an array, num, and x as arguments into the function. where the array is the given array of elements, num is the size of the array and x is the key to search. here we assume starting index is 0 and the last index is size-1. If there is only one element i.e s=e, we will return the index. If this is not fulfilled, we will search by the above formula. If the element is at the index computed using the formula pos, return the index pos. Make the starting index pos+1, if the element at pos is less than x. Make the ending position as pos-1, if the element at pos is greater than x.
Submitted by Kothapally Nehasai (Neha1292)
Download packets of source code on Coders Packet