Searching Algorithms Questions Medium
Interpolation search is a searching algorithm that is used to find a specific element in a sorted array or list of elements. It is an improvement over binary search as it makes intelligent guesses about the location of the target element based on the values of the elements in the array.
In interpolation search, instead of always dividing the search space in half like in binary search, it estimates the position of the target element by using a formula that takes into account the values of the first and last elements in the array, as well as the target element itself. This estimation allows the algorithm to make a more informed decision about where to search for the target element.
The formula used in interpolation search is:
position = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
Here, 'low' and 'high' represent the indices of the first and last elements in the array, 'target' is the element being searched for, and 'arr' is the sorted array.
Once the position is calculated, the algorithm compares the target element with the element at that position. If they match, the search is successful. If the target element is smaller, the algorithm narrows down the search space to the left side of the array. If the target element is larger, the algorithm narrows down the search space to the right side of the array. This process continues until the target element is found or the search space is exhausted.
Interpolation search has an average time complexity of O(log log n) when the elements are uniformly distributed. However, in worst-case scenarios where the elements are unevenly distributed, the time complexity can degrade to O(n), making it less efficient than binary search.