# Interpolation search

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.

## Description

The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position , where the value should be placed in accordance to the distribution of values a splits the array at . If the array contains numbers and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in .

## Code

/** * Interpolation search * @param array array with uniformly distributed values in ascending order * @param value searched value * @param from first index that might be touched * @param to last index that might be touched * @return index index of the searched value in the array, -1 if not found */ public static int interpolationSearch(int[] array, int value, int from, int to){ if(array[from] == value) return from; else if(from == to || array[from] == array[to]) return -1; //not found //probable position of the searched value int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]); if(array[index] == value) return index;//found //continue in the right part of the array else if(array[index] < value) return interpolationSearch(array, value, index + 1, to); //continue in the left part of the array else return interpolationSearch(array, value, from, index - 1); }

Tweet | ||

Rating (0):
0