Interpolation Search

Interpolation Search works better than binary search for uniformly distributed and sorted array

binary search always see in the middle of the array but interpolation search calculates a position where the value should be placed according to the distribution of values in the given array so it found the middle index by

mid = low + ((toFind – sortedArray[low]) * (high – low)) / (sortedArray[high] – sortedArray[low]);

Interpolation search on average makes log(log(n)) comparison but its worst case is O(n)

java implementation of the above algorithm

https://ideone.com/4pxceg

Advertisements