# TADM2E 4.31

From Algorithm Wiki

Revision as of 18:23, 11 September 2014 by Algowikiadmin (Talk | contribs)

**Part -1** Since set is sorted the max element will lie at position

Since set is sorted the max element will lie at position Max = Set[k] where k != 0 Set[n] where K == n

**Part -2 ** Apply binary search to find out transition point

Assume set indexes are zero based FindNumberOfRotations(A): 1. if (A[0] < A[n-1]) then There is no rotation made return 0 2. low = 0, high =1 3. mid = (low + high)/2 4. if(A[mid] < A[high]) then Transition lies in left half of the array if A[mid-1] > A[mid] then return mid else high = mid-1 Go to step 3. else Transition lies in right half of array if(A[mid] > A[mid+1]) then return mid+1 else low = mid+1 Go to step 3