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

Question

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

Answer 1

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.