Interpolation search algorithm in Javacsript

Interpolation search is a search algorithm that uses a mathematical formula to calculate the approximate location of a target value in a sorted array. Unlike binary search, interpolation search doesn’t require the array to be divided into equal halves during each iteration, instead it calculates the midpoint based on the target value and the range of values in the array.

Interpolation search can be thought of as a smart version of a normal search. Imagine you’re searching for a book in a library. In a normal search, you’d check each and every shelf until you find the book you’re looking for. But in an interpolation search, you’ll use some extra information about the book to help you find it faster. For example, if you know the book’s author and publication date, you can estimate where the book should be located in the library, and then check just that section for the book. This way, you can find the book much faster than if you were searching each and every shelf. Similarly, in interpolation search, we use extra information about the target value (such as its range in the array) to estimate where the value could be located, and then check that section instead of checking the entire array.

Here is an example implementation of interpolation search in JavaScript:

function interpolationSearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right && target >= arr[left] && target <= arr[right]) {
    const position = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
    const mid = Math.floor(position);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Explanation of each line:

• let left = 0, right = arr.length - 1;: Declare two variables left and right which will keep track of the start and end indices of the subarray being searched. left is initialized to 0 and right is initialized to arr.length - 1, meaning the entire array will be searched.
• while (left <= right && target >= arr[left] && target <= arr[right]): This while loop continues until the target value is found or the search subarray becomes empty. The && conditions ensure that the target value is within the bounds of the current subarray.
• const position = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);: This line calculates the estimated position of the target value within the array. The formula takes the difference between the target value and the value at the left index, multiplies it by the difference between the right and left indices, and divides it by the difference between the values at the right and left indices.
• const mid = Math.floor(position);: Math.floor is used to round down the estimated position to the nearest integer. This integer represents the index of the estimated midpoint of the search subarray.
• if (arr[mid] === target): If the value at the estimated midpoint is equal to the target value, the target value has been found and the index is returned.
• else if (arr[mid] < target): If the value at the estimated midpoint is less than the target value, the target value is likely in the right half of the search subarray, so left is updated to mid + 1 and the search continues.
• else: If the value at the estimated midpoint is greater than the target value, the target value is likely in the left half of the search subarray, s right is updated to mid - 1 and the search continues.
• return -1;: If the target value is not found, -1 is returned to indicate that the target value is not in the array.

The limitations of the Interpolation Search algorithm include:

• The array must be sorted in ascending order.
• The values stored in the array must be uniformly distributed.
• The algorithm can be slow for arrays with non-uniformly distributed values.
• The algorithm can be slow for arrays with very large values, as the proportional position calculation can cause overflow.