# 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