A searching method that uses linear interpolation can give fast retrieval when the ordered data set is relatively evenly distributed over its range of possible values. With this method. the magnitude of the value x we are seeking is used to determine which element of the array we should next compare with x. When lower and upper are the current limits of the array segment left to be searched we can examine next the element that is approximately a distance
Above the current value of lower. Implement an interpolation search and compare its performance with the log2 n performance of the binary search. Use a uniform random number generator to produce the array a. Note that this array will need to be sorted.