howeverin case the values are not equal then depending on the comparisonthe remaining search space is reduced to the part before or after the estimated position thuswe see that interpolation search is similar to the binary search technique howeverthe important difference between the two techniques is that binary search always selects the middle value of the remaining search space it discards half of the values based on the comparison between the value found at the estimated position and the value to be searched but in interpolation searchinterpolation is used to find an item near the one being searched forand then linear search is used to find the exact item the algorithm for interpolation search is given in fig figure helps us to visualize how the search space is divided in case of binary search and interpolation search low val item to be searched high middle (lowhigh)/ (abinary search divides the list into two equal halves low val item to be searched middle low (high lowy(key [low]/( [higha[low])high (binterpolation search divides the list into two equal halves figure difference between binary search and interpolation search complexity of interpolation search algorithm when elements of list to be sorted are uniformly distributed (average case)interpolation search makes about log(log ncomparisons howeverin the worst casethat is when the elements increase exponentiallythe algorithm can make up to (ncomparisons example given list of numbers [{ search for value using interpolation search technique solution low high val [low [high middle low (high low) ((val [low]/( [higha[low) +( (( ( [middlea[ which is equal to value to be searched programming example write program to search an element in an array using interpolation search #include #include #define max int interpolation_search(int []int lowint highint valint midwhile(low <highmid low (high low)*((val [low]( [higha[low]))if(val = [mid]return midif(val [mid]