算法描述:
Suppose an array sorted in ascending order 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.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
解题思路:二分法,注意细节。
if(nums.size()==1) return nums[0]; int left = 0; int right = nums.size()-1; while(left < right){ if(nums[left] < nums[right]) return nums[left]; int mid = left + (right - left) / 2; if(nums[mid] > nums[right]){ left = mid +1; } else right = mid; } return nums[left]; }