Interpolation Search is a searching algorithms which works on sorted array.
It works best for arrays where elements are uniformly distributed.
At every iteration it finds the position to search using $$pos = low + \frac{(key - arr[low]) * (high - low)}{(arr[high] - arr[low])}$$
If element at the position is equal to the key, search stops.
If the element at position is greater than the key, search continues in the first part. Otherwise search continues in the second part.
It has best case complexity of O(1), average case complexity of O(log(log n)) and worst case complexity of O(n).