﻿ 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);
}
```