Question $2$: A 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 subarrays 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 $+2,$ the interpolation search

estimates the position of the array$$s element at which the sorted array should be divided as $+$

$([[]])([])$

$($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.

$($c$)$ 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