5.1

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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


Back to Chapter 5