top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+2 votes
1,157 views
how to find the fastest way to locate the largest element in a circular sorted array ?
posted Sep 13, 2013 by Vinay Shukla

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
Do we need to find or insert  the element in order ?

1 Answer

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

answer Sep 14, 2013 by Arvind Singh
Similar Questions
+2 votes

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.

+3 votes

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...