Leetcode上的一道题。在rotated array中找到最小值。一个rotated array就是一个已排序好的数组绕着某个位置旋转180度，像[1,2,3,4,5,6]，绕着5旋转后就是[5,6,1,2,3,4]。
用二分法找最小值，因为这个数组可以看成两个已排序的数组的组成的，而且旋转到后面的数组鄂最大值小于等于之前的最小值，那么我们就可以用二分法，初始值 l = 0，r = nums.size()。mid = (l + r) / 2。如果nums[l] < nums[mid]。说明[l,mid]在同一个递增数组内。i = mid。反之，则 j= mid。
下面是C++实现的版本
class Solution {
public:
int findMin(vector<int>& nums) {
int i = 0,j = nums.size() - 1,mid;
while(i < j - 1)
{
mid = (i + j) / 2;
if(nums[i] > nums[mid])
j = mid;
else
i = mid;
}
int ans = min(nums[0],nums[nums.size() - 1]);
return min(ans,min(nums[i],nums[j]));
}
};
用Python又实现一遍，不得不说C++要比Python快好多
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
while(l < r - 1):
mid = int((l + r) / 2)
if nums[l] > nums[mid]:
r = mid
else:
l = mid
ans = min(nums[0],nums[len(nums) - 1])
return min(ans,min(nums[l],nums[r]))
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/20740.html