# 5.1

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