# how to find the fastest way to locate the largest element in a circular sorted array ?

1,168 views
how to find the fastest way to locate the largest element in a circular sorted array ?
posted Sep 13, 2013

Do we need to find or insert  the element in order ?

+1 vote

A circularly sorted array is an a sorted array which has been rotated in some direction by some moves. A fast way is to modify binary search to find the largest element which will give Log(N) complexity (this may not be the fastest technique).

``````static int LargestElement<T>(IList<T> A)
where T : IComparable<T>
{
if (A.Count == 0)
return -1;
int l = 0;
int h = A.Count - 1;
while (A[l].CompareTo(A[h]) > 0)
{
int m = l + (h - l) / 2;
if (A[l].CompareTo(A[m]) < 0)
l = m + 1;
else
h = m;
}
return h;
}
``````

The algorithm repeatedly tries to cut the Array into two by inspecting the end and middle elements. It then looks for half where first element is greater than the last element. The half with the discontinuity is the half with largest value resides. The algorithm terminate when A[l] < A[h] this means the whole range is under consideration is ordered and the largest element must be at A[h]. The algorithm will return the index of largest element or -1 if the input array has zero elements.

Similar Questions

1,1,2,2,2,6,6,6,7,7,7,7,7,7,7,8,8,9,9,9

Example:
Input = 1 Output=0 (First index of 1).
Input = 2 Output=2 (First index of 2).
Input = 6 Output= 5 (First index of 6).
Input = 7 Output= 8 (First index of 7).
Input = 8 Output=15 (First index of 8).
Input = 9 Output=17 (First index of 9).

+1 vote

Given 3 sorted array of size x, y, z. what is the minimum time taken to find the kth smallest element in the merged sorted array.