Interpolation Search

Definition

Definition

Interpolation Search is an efficient searching algorithm that works on sorted arrays. It improves on binary search by using interpolation to find the probable position of the target value

Explanation

Calculate the probable position of the target value using the interpolation formula. Then, compare the target value with the element located at this probable position. If they match, return the index of the element. If the target value is greater than the element at the probable position, continue the search in the right subarray. Conversely, if the target value is smaller, search the left subarray. Continue this process until the element is found or the subarray reduces to an empty array

Guidance

• To find where the target value might be, consider where it falls between the lowest and highest values in the array
• Check if the value at this estimated position matches the target value
• If it does, you've found the target value
• If the estimated value is greater than the target, look in the lower half of the remaining array
• If the estimated value is smaller than the target, look in the upper half
• Repeat these steps until you find the target or you've searched through the entire array without finding it

Tips

• interpolation Search performs well when the elements in the array are uniformly distributed
• it's more effective on large arrays than binary search, particularly if the elements are evenly distributed

Practice

Practice

interpolationSearch(arr, x):
  low = 0
  high = length(arr) - 1

  while low <= high and x >= arr[low] and x <= arr[high]:
    pos = low + ((high - low) / (arr[high] - arr[low])) * (x - arr[low])

    if arr[pos] == x:
      return pos
    elif arr[pos] < x:
      low = pos + 1
    else:
      high = pos - 1

  return -1

Solution

package main

func interpolationSearch(arr []int, x int) int {
    low := 0
    high := len(arr) - 1

    for low <= high && x >= arr[low] && x <= arr[high] {
        if low == high {
            if arr[low] == x {
                return low
            }
            return -1
        }

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

        if arr[pos] == x {
            return pos
        }

        if arr[pos] < x {
            low = pos + 1
        } else {
            high = pos - 1
        }
    }

    return -1
}

public class InterpolationSearch {

  public static int interpolationSearch(int[] arr, int x) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high && x >= arr[low] && x <= arr[high]) {
      if (low == high) {
        if (arr[low] == x) {
          return low;
        }
        return -1;
      }

      int pos = low + ((x - arr[low]) * (high - low) / (arr[high] - arr[low]));

      if (arr[pos] == x) {
        return pos;
      }

      if (arr[pos] < x) {
        low = pos + 1;
      } else {
        high = pos - 1;
      }
    }

    return -1;
  }
}

function interpolationSearch(arr, x) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high && x >= arr[low] && x <= arr[high]) {
    if (low === high) {
      if (arr[low] === x) {
        return low;
      }
      return -1;
    }

    let pos =
      low +
      Math.floor(((x - arr[low]) * (high - low)) / (arr[high] - arr[low]));

    if (arr[pos] === x) {
      return pos;
    }

    if (arr[pos] < x) {
      low = pos + 1;
    } else {
      high = pos - 1;
    }
  }

  return -1;
}

fun interpolationSearch(arr: IntArray, x: Int): Int {
    var low = 0
    var high = arr.size - 1

    while (low <= high && x >= arr[low] && x <= arr[high]) {
        if (low == high) {
            return if (arr[low] == x) low else -1
        }

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

        if (arr[pos] == x) return pos

        if (arr[pos] < x) low = pos + 1
        else high = pos - 1
    }

    return -1
}

def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high and x >= arr[low] and x <= arr[high]:
        if low == high:
            if arr[low] == x:
                return low
            return -1

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

        if arr[pos] == x:
            return pos

        if arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1

    return -1

fn interpolation_search(arr: &[i32], x: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len() - 1;

    while low <= high && x >= arr[low] && x <= arr[high] {
        if low == high {
            return if arr[low] == x { Some(low) } else { None };
        }

        let pos = low + ((x - arr[low]) * (high - low) as i32 / (arr[high] - arr[low])) as usize;

        if arr[pos] == x {
            return Some(pos);
        }

        if arr[pos] < x {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }

    None
}

function interpolationSearch(arr: number[], x: number): number {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high && x >= arr[low] && x <= arr[high]) {
    if (low === high) {
      return arr[low] === x ? low : -1;
    }

    let pos =
      low +
      Math.floor(((x - arr[low]) * (high - low)) / (arr[high] - arr[low]));

    if (arr[pos] === x) {
      return pos;
    }

    if (arr[pos] < x) {
      low = pos + 1;
    } else {
      high = pos - 1;
    }
  }

  return -1;
}