TADM2E 4.31

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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>