Consider an array A of n distinct integers (that is, all elements are different)
ID: 3602154 • Letter: C
Question
Consider an array A of n distinct integers (that is, all elements are different). It is known that A was originally sorted in ascending order, but A was then right-rotated r places, where 0 < r < n. In other words, the last r elements were moved from the end of the array to the beginning, with all other elements being pushed r positions to the right. For example, for n = 7 and r = 3, the result may look like this:
[43, 46, 58, 12, 20, 29, 34]
For r = 5, the result, based on the same original array, would be
[29, 34, 43, 46, 58, 12, 20]
You know that the given A[0..n1] has this particular form, that is, for some r, the sequence A[r], . . . , A[n 1], A[0], . . . A[r 1] is in ascending order, but you do not know what r is. Design an algorithm to find the largest integer in A. Write an algorithm that works in time O(log n)
Explanation / Answer
Afte the rotation the array consists of an increasing sequence ending at the maximum element and followed by another increasing sequence with all elements less than the ones in first sequence, so the algorithms works as below
1) take the mid element of the array and compare it with elements on its right and right most. if both are less than the element then it is the max, return it.
2) if rightmost < element < right then then max is present right to this element, so repeat the above process with the second half of the array.
3) else if element< right < rightmost then then max is present left to this element repeat above process with first half of array.
TIme complexity
---------------------------
In each iteration the algorithm works with half the data in previous iteration so it runs in O(logn)