The Interpolation Search is an improvement over Binary Search for instance, where the values in a sorted array are uniformly distributed. Binary Search always goes to middle element to check. On the other hand, interpolation search may go to different locations according the value of key being searched.