The Gateway to Computer Science Excellence
+2 votes
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.)
in Algorithms by Boss (17.5k points)
retagged by | 48 views

1 Answer

0 votes

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,373 answers
198,512 comments
105,286 users