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

</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[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

</pre>