Subject- Algorithms : Techniques and Theory

2. (15 points total) This question is concerned with the problem of searching a length-n array A (indexed from 0 ) that is a cyclic rotation of a sorted array (see the definition of "nice" below). For any indices i and j such that 0ijn, we write A[i,j] to refer to the length- (ji) subarray of A consisting of elements A[i] through A[j1]. We say that array A[i,j] is nice if there is an index k in {i,,j} such that the array obtained by appending subarray A[i,k] to subarray A[k,j] is sorted in nondecreasing order. (a) (10 points) Recall that binary search can be used to search a sorted array of length n for a given value in O(logn) time. Show how to modify the usual binary search algorithm to obtain an O(logn)-time algorithm for searching a nice array A[0,n] with distinct entries. Justify the correctness and time complexity of your algorithm. (b) (5 points) For many computational problems related to comparison-based sorting, the asymptotic complexity is essentially the same whether or not duplicate entries are allowed. For example, binary search of a length- n sorted array runs in O(logn) time whether or not there are duplicate entries. What about the problem considered in this question? That is, if we repeat part (a), but drop the requirement that the entries in A be distinct, can we still solve the search problem in O(logn) time? Justify your answer. Clarifying remarks: To justify a "yes" answer, you should extend your work from part (a) to the more general setting in which ties are permitted. To justify a "no" answer, you should establish a (logn) lower bound