variant of binary search algorithm is called interpolation search. Similar to the binary search algorithm, it works on a sorted array of elements by dividing it into two subarrays and compare a search key with an element at which the sorted array was divided. However, unlike the binary search algorithm, the interpolation search algorithm does not divide the sorted array into two even subarrays. It$,$ instead, uses the values of the search key to decide at which array's element the sorted array should be divided into two uneven suharrays and then compare the search key with that element. More formally, instead of calculating the midpoint element of the sorted array, in the binary search algorithm, as low$+$ah$-$low, the interpolation search estimates the position of the array's element at which the sorted array should be divided as low $+$ Alhighl$-$Allow$)($a$)$ Based on the above description of the interpolation search algorithm, write down its pseudocode.$($b$)$ Under which algorithms design paradigm would you classify the interpolation search algorithm? Justify your answer.$[$ey Give characterizations of the worst$-$case input for the interpolation search and show through example that the algorithm is linear $($n$)$ in the worst$-$case.$($d$)$ Give characterizations of the best$-$case input for the interpolation search and show through example that the algorithm is log log n in the best$-$case.$($e$)$ For the application of Phone Book, contacts are arranged in sorted order and nearly uniform. If you were asked to recommend one of the two algorithms $($binary search and interpolation search$),$ which one would you recommend and why?