interpolation search Algorithm
Interpolation search is an efficient algorithm for searching a specific value within a sorted array of values. This search algorithm takes advantage of the sorted nature of the array by estimating the position of the target value based on the values at the beginning and end of the array, and the relative size of the target value. The basic idea is to use the target value to calculate a likely position within the array where the value might be found, and then narrow down the search range accordingly. This approach allows the algorithm to find the target value more quickly than other search algorithms, such as linear search or binary search, especially when dealing with large arrays with uniformly distributed values.
The interpolation search algorithm starts by calculating the position of the target value using a linear interpolation formula, which involves the first and last elements of the search range, and the target value itself. This position acts as a guess for the location of the target value in the array. Based on this guess, the algorithm determines whether the target value is before, after, or at the guessed position. If the target value is found, the algorithm returns the index of the target value. If the target value is before or after the guessed position, the search range is updated accordingly, and the interpolation search process is repeated within the new search range. This process continues until the target value is found, or the search range becomes empty, indicating that the target value is not in the array. As the search range narrows down with each iteration, the interpolation search algorithm converges to the target value more rapidly than linear or binary search algorithms.
#include<iostream>
// function to search the value in an array using interpolation search
int search(int arr[], int value, int len) {
int low = 0, high, mid;
high = len-1;
while (arr[low] <= value && arr[high] >= value) {
mid = (low + ((value-arr[low])*(high-low)) / (arr[high]-arr[low]));
if (arr[mid] > value)
high = mid-1;
else if (arr[mid] < value)
low = mid+1;
else
return mid;
}
if (arr[low] == value)
return low;
return 0;
}
int main() {
int n, value, array[100], re;
std::cout << "Enter the size of array(less than 100) : ";
std::cin >> n;
std::cout << "array in ascending (increasing) order : " << std::endl;
for (int i=0; i < n; i++)
std::cin >> array[i];
std::cout << "Enter the value you want to search : ";
std::cin >> value;
re = search(array, value, n);
if (re == 0)
std::cout << "Entered value is not in the array" << std::endl;
else
std::cout << "The value is at the position " << re << std::endl;
return 0;
}
