Find Minimum 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.
You may assume no duplicate exists in the array.
考え方は簡単で、二分法です.単調であればnums[left]nums[left]の場合、最小値はmid右側、nums[mid]の場合
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
考え方は簡単で、二分法です.単調であればnums[left]
public int findMin(int[] nums) {
return binaryFind(nums,0,nums.length-1);
}
public int binaryFind(int[] nums,int left,int right) {
// TODO Auto-generated method stub
if(left==right)
return nums[left];
if(nums[left]<nums[right])
return nums[left];
int mid=(left+right)/2;
if(nums[mid]>nums[left])
return binaryFind(nums, mid+1, right);
else if(nums[mid]==nums[left])
return Integer.min(nums[left],nums[right]);
else
return binaryFind(nums, left, mid);
}