Difference between revisions of "TADM2E 4.31"
Revision as of 18:13, 11 September 2014
Part -1 Since set is sorted the max element will lie at position <pre> 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 <pre> Assume set indexes are zero based FindNumberOfRotations(A):
1. if (A < 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