Find Minimum element in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
Discussion :
Case 1 : No duplicate exists in the array
Case 2 : Duplicate exists in the array
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
Discussion :
Case 1 : No duplicate exists in the array
public int findMin(int[] num) { int start = 0, end = num.length-1; while(start<end) { int mid = start+(end-start)/2; if(num[mid]<num[end]) end = mid; else start = mid+1; } return num[start]; }
Case 2 : Duplicate exists in the array
public int findMin(int[] num) { int start = 0, end = num.length-1; while(start<end) { int mid = start+(end-start)/2; if(num[mid]<num[end]) end = mid; else if(num[mid]>num[end]) start = mid+1; else end--; } return num[start]; }
Comments
Post a Comment