In searching for the placement of a key x ̄ in a sorted array x(i), i = 1,2,...,n, binary search partitions the current search domain into two subdomains by always selecting the mid-point index n/2 (or (n+1)/2, if n is odd) of the array. Clearly, binary search does not take into consideration the key value x ̄ in selecting this mid-point.
A simple variation of binary search, called interpolation search, is based on partitioning the current search domain such that the “mid-point” index is guessed by assuming a linear interpolation of the indices between the first key value x(1) and last key value x(n).
create a new function isearch which implements the
interpolation search algorithm.