 template 
int interpolation_search(T arr[], int size, T key)

Notice that having probed the list at index "mid", for reasons of loop control administration, this code sets either "high" or "low" to be not "mid" but an adjacent index, which location is then probed during the next iteration.Since an adjacent entry's value will not be much different, the interpolation calculation is not much improved by this one step adjustment, at the cost of an additional reference to distant memory such as disk.Each iteration of the above code requires between five and six comparisons (the extra is due to the repetitions needed to distinguish the three states of < > and = via binary comparisons in the absence of a three-way comparison) plus some messy arithmetic, while the binary search algorithm can be written with one comparison per iteration and uses only trivial integer arithmetic.