hkucuk

Interpolation Search Algorithm

July 12, 2023 • ☕️ 3 min read • 🏷 computer, software, search

Translated by author into: English


Interpolation Search is a search algorithm used to quickly search an ordered array. While this algorithm works on ordered arrays such as binary search, it relies on an approximate location to find the sought value.

It is based on two basic conditions:

  1. The array must be sequential.
  2. Differences between elements in the array should be predictable and should not be irregular.

How Does Interpolation Search Work?

The interpolation search algorithm uses a formula to calculate the estimated location of the searched value. This formula is usually as follows:

position = low + ((value - arr[low]) / (arr[high] - arr[low])) * (high - low)

Here:

  • arr[] => array of items to be searched.
  • low => represents the starting directory index.
  • high => represents the ending directory index.
  • value => represents the sought value.

The algorithm follows these steps:

  1. Initially, the low and high values represent the start and end indexes of the array.
  2. The above formula is used to calculate the estimated position.
  3. If the estimated value is equal to the searched value, the search is successful and the estimated location is returned.
  4. If the estimated value is less than the searched value, the search continues on the right, ie the low value is updated.
  5. If the estimated value is greater than the searched value, the search continues on the left, ie the high value is updated.
  6. This process continues until the sought value is found or the low value is greater than the high value.

Comparison with Some Other Search Algorithms

  • Linear Search: The linear search algorithm is used for sequences that are not ordered or are not ordered, even if they are ordered. It checks each element in turn. Interpolation search offers a faster alternative because it can quickly approximate elements using the estimated position. Its complexity is O(n).
  • Binary Search: Binary search checks for the element in the middle of the array at each step. Interpolation search makes a faster guess using the estimated differences between elements. However, performance may degrade in arrays with irregular intervals. Its complexity is O(log n).
  • Jump Search: Jump search scans a range in jump steps. While the steps of the jump search are fixed, the steps of the interpolation search vary according to the difference of the estimated position. Its complexity is O(√ n).

Interpolation search can be faster than binary search if the array is evenly distributed. However, if the differences between array elements are large and irregular, the algorithm may not make accurate predictions and may even be slower than binary search.

Complexity

  • Time: O(log(log(n))

Implementation of Interpolation Search Algorithm in GoLang:

package main

import (
	"fmt"
)

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

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

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

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

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

	return -1
}

func main() {
	arr := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
	target := 11

	index := interpolationSearch(arr, target)
	if index != -1 {
		fmt.Printf("The searched value was found in %d index.\n", index)
	} else {
		fmt.Println("The searched value was not found.")
	}
}

This example applies the Interpolation Search algorithm on a given ordered array. The interpolationSearch function takes the array and target value and returns the index of the target value in the array. Returns -1 if the target value is not found. In this example, the searched value is 11 and the given string is [1, 3, 5, 7, 9, 11, 13, 15, 17, 19].

When the program is run, the output will be as follows.

The searched value was found in 5 index.

The running version of the program can be accessed from here.

Resources