CMI2018-B-4

Question

You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by $2$ positions.
Give an $O(\log n)$ time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)

Answer 1

Let the number of elements be $n$ in the given array. Now, if the array is not shifted at all then the last element would be the largest.

Now, since the array is shifted by some $m$ degree. Therefore, we will broadly classify the problem into two parts

$i.$ Left part when $m> 0$ and $m < \frac{n}{2}$.

$ii.$ Right part when $m >= 0$

So in case $(i)$ the largest element lies in the left part and the in the case $ii$ the largest element lies in the right part.

So, this problem reduces to a recursive approach which divides the problem into two parts at each call. Hence, the time complexity would be

$O(logn)$.

The general call function would be largeFind(arr, 0, n-1)

pseudo code would be:

 

largeFind(arr, si, ei)

if(arr[si] <= arr[ei])

    return arr[ei]

else 

{

    mid = si + (ei-si)/2

        if(arr[mid] > arr[mid+1]

            return arr[mid]

        else if (arr[si] > arr[mid])

            return largeFind (arr, si, mid-1)

        else if (arr[mid] >= arr[ei])

            return largeFind(arr, mid+1, ei)

}

 

Answer 2