Here is a version of binary search that returns the index of

Here is a version of binary search that returns the index of the element if it is found, or -1 if the element is not found. def binary_search(A, x): \' \' \' Pre: list A is sorted in ascending order and has no duplicate elements Post: return the index of x in A if exists; return -1 otherwise. \' \' \' if len(A) 0: return -1 m = len (A)//2 if A [m] x: return m elif A[m] > x: return binary_search(A [0. .m-1], x) else: result = binary.search(A[m+1..len(A)-1], x) if result -1: return -1 else: return result + m + 1 (a) Write the recurrence for the worst-case runtime T(n) of the algorithm, and use the master theorem to find the asymptotic upper-bound on T(n). State clearly which case of the master theorem applies. (b) Prove that this algorithm is correct.

Solution

(a) The recurrence for binary search is T (n) = T (n/2) + (1).

Using Master Theorem, a = 1,b = 2,f(n) = (1). Now f(n) = (1) = (n^{logb a}) = (n⁰ ) = (1). Using the second form of Master Theorem, T (n) = (n⁰log n) = (log n).

(b) The algorithm is correct becuase in each iteration it checks the middle item, if middle item matches the term to be searched, then we return its index, else, we reject all elements from the second part of the list and start searching in the first part of the list.