48 views
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.)

retagged | 48 views

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)

}

by Boss (19.1k points)
edited by