Solve 1(b)

With limit of worst case time complexity as O(logn)

Problem 2-1. [30 points) Given an element x and a sorted array A, the problem of determining whether x is in A or not can be solved efficiently by a binary search algorithm. Consider a variation of binary search in which we divide the array A into k equal pieces. The search then continues recursively in one of these pieces, if needed. (a) [10 points) Let k = 3. Give a full description of the variation as suggested above. Determine the worst-case running time of this algorithm. Is it better or worse than the original binary search algorithm? Be precise and justify your answer. (b) (20 points) Answer the same questions as in part (a) with k = vn, where n is the length of A