The Gateway to Computer Science Excellence

+2 votes

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

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

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) }

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,373 answers

198,512 comments

105,286 users