Difference between revisions of "TADM2E 4.31"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

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
</pre>
Part 2 Apply binary search to find out transition point <pre> Assume set indexes are zero based FindNumberOfRotations(A):
1. if (A[0] < A[n1]) 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[mid1] > A[mid] then return mid else high = mid1 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
</pre>