Difference between revisions of "TADM2E 4.31"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
'''Part -1''' Since set is sorted the max element will lie at position | '''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 | Since set is sorted the max element will lie at position | ||
Max = Set[k] where k != 0 | Max = Set[k] where k != 0 | ||
Set[n] where K == n | Set[n] where K == n | ||
| − | + | </pre> | |
'''Part -2 ''' Apply binary search to find out transition point | '''Part -2 ''' Apply binary search to find out transition point | ||
| − | + | <pre> | |
Assume set indexes are zero based | Assume set indexes are zero based | ||
FindNumberOfRotations(A): | FindNumberOfRotations(A): | ||
| − | 1. if (A[0] | + | 1. if (A[0] < A[n-1]) then |
There is no rotation made return 0 | There is no rotation made return 0 | ||
2. low = 0, high =1 | 2. low = 0, high =1 | ||
3. mid = (low + high)/2 | 3. mid = (low + high)/2 | ||
| − | 4. if(A[mid] | + | 4. if(A[mid] < A[high]) then |
Transition lies in left half of the array | Transition lies in left half of the array | ||
| − | if A[mid-1] | + | if A[mid-1] > A[mid] then return mid |
else | else | ||
high = mid-1 | high = mid-1 | ||
| Line 22: | Line 22: | ||
else | else | ||
Transition lies in right half of array | Transition lies in right half of array | ||
| − | if(A[mid] | + | if(A[mid] > A[mid+1]) then return mid+1 |
else | else | ||
low = mid+1 | low = mid+1 | ||
Go to step 3 | Go to step 3 | ||
| − | + | </pre> | |
Latest revision as of 18:23, 11 September 2014
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
