It is given a sorted circularIy shifted array. This is an array of sorted unique
ID: 3782308 • Letter: I
Question
It is given a sorted circularIy shifted array. This is an array of sorted unique integers such that each eIement has been shifted k positions to the right with eIements wrapping around. In other words if the Iength of the array is L, the vaIue at index i in the sorted array will be at index (i+k) % L in the sorted circularIy shifted array.
Write pseudocode such that if you are given a sorted circuIarly shifted array, you wiII return the maximum eIement.
The code must run asymptotically faster than (n).
Suppose you are given a sorted circularly shifted array. This is an amay of sorted unique integers such that each element has been shifted k positions to the right with elements wrapping around. In other words if the length of the array is L. the value at index iin the sorted array will be at Index (+k)% L in the sorted circularly shifted array. Write pseudo-code such that if you are given a sorted circularly shifted amay, you will return the maximum element. You code must run asymplotically faster than en)Explanation / Answer
Hi, Please find my algorithm. It takes O(logN) time.
Please let me know in case of any issue.
We can do it in O(Logn) using Binary Search. If we take a closer look , we can easily figure out following pattern: The minimum element is the only element whose previous element is greater than it. If there is no such element, then there is no rotation and first element is the minimum element. Therefore, we do binary search for an element which is smaller than the previous element.
int findMax(int arr[], int low, int high)
{
// This condition is needed to handle the case when array is not
// rotated at all
if (high < low) return arr[high];
// If there is only one element left
if (high == low) return arr[low];
// Find mid
int mid = low + (high - low)/2;
// Check if element mid is maximum element. Consider
// the cases like {3, 4, 5, 1, 2}
if (mid < high && arr[mid+1] < arr[mid])
return arr[mid];
// Check if (mid-1) is maximum element
if (mid > low && arr[mid] < arr[mid - 1])
return arr[mid-1];
// Decide whether we need to go to left half or right half
if (arr[high] > arr[mid])
return findMax(arr, low, mid-1);
return findMax(arr, mid+1, high);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.