(Solved): in python please Design and implement a program that implements an Interpolation Search method. Inte ...

Design and implement a program that implements an Interpolation Search method. Interpolation search is similar to binary search, except it tries to begin the search nearer to the location of the item. Instead of the using the middle value of the sorted array, interpolation search estimates the location of the target with respect to the first \& last values in the array. The implementation is the same as binary search except that you should calculate the mid value as: $\begin{array}{l}\mathrm{mid}=\text{ first + ((last - first) }{}^{?}(\text{ searchKey - }\\ \mathrm{arr}[\text{ first }]))/\text{ ( arr [last] - arr[first] ) }\end{array}$ Note that Interpolation Search will only work with numeric types! Your interpolation search method should work on an array of integers