Difference between pages "Chapter 1" and "5.1"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "Problems *1.1 *1.2 *1.3 *1.4 *1.5 *1.6 *1.7 *1.8 *1.9 *1.10 *1.11 *1.12 *1.13 *1.14 *1.15 *1.16...") |
(Created page with "'''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...") |
||
| Line 1: | Line 1: | ||
| − | + | '''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> | ||
| − | |||
| − | + | Back to [[Chapter 5]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Latest revision as of 00:53, 21 September 2020
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
