In binary search algorithm, we always start with the middle of the array to start the searching process. If an array is uniformly distributed and we are looking for an item, which, may be close to the end of array, then searching from the middle might not sound like a good choice to us. Interpolation search can be very helpful in such cases. Interpolation search is an improvement over binary search algorithm. Interpolation search may go to different location based on the value of the searched key. For example, if we are searching a key that is close to the beginning of the array, it will go to the first part of the array instead of starting from the middle. The position is calculated using a probe position calculator equation, which looks like this:

pos = low + [ (key-arr[low])*(high-low) / (arr[high]-arr[low]) ]

As we can see, we are going from our generic mid = (low+high)/2 equation to a more complex looking equation. This formula will return a higher value if the searched key is closer to arr[high] and a much lower value if the key is closer to arr[low]. Now, let's implement this search method with the help of our binary search code:

function interpolationSearch(array $arr, int $key): int { 
    $low = 0; 
    $high = count($arr) - 1; 

    while ($arr[$high] != $arr[$low] && $key >= $arr[$low] && 
      $key <= $arr[$high]) { 

    $mid = intval($low + (($key - $arr[$low]) * ($high - $low) 
    / ($arr[$high] - $arr[$low]))); 

      if ($arr[$mid] < $key) 
          $low = $mid + 1; 
      else if ($key < $arr[$mid]) 
          $high = $mid - 1; 
      else 
          return $mid; 
    } 

    if ($key == $arr[$low]) 
      return $low; 
    else
      return -1; 
}

Here, we are calculating in a different way. Though it is taking more computational steps, the good part is that if the list is uniformly distributed, then the average complexity of this algorithm is O(log (log n)), which is much better compared to binary search's complexity of O(log n). Also, we have to be careful if the distributions of the keys are not uniform. In this case, the performance of the interpolation search could degrade.

Now, we will explore another variation of binary search known as exponential search, which can improve the algorithm.