Desirable condition for interpolation search is that the array should be sorted and the values should be uniformly distributed. The algorithm would fail to give the correct result if array is not sorted.

(T(n) = T(n/2) + theta(1))

Using the divide and conquer master theorem, we get the time complexity as O(logn).

Trace the input with the binary search iterative code.

Iteration1 : mid = 77; Iteration2 : mid = 88;

Since 'mid' is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.

In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.

T(n) = T(n/2) + 1, Using the divide and conquer master theorem.

Using the divide and conquer master theorem.

At first level key = 90

At second level key= 99

Here 90 and 99 are mid values.

level 1: mid = 7

level 2: mid = 99

level 3: mid = 899(this is the key).

A recursive approach is easier to understand and contains fewer lines of code.