159. 寻找旋转排序数组中的最小值
2021-05-06 01:26
标签：sample 情况 panel art 输入 判断 cti 测试数据 bar 假设一个排好序的数组在其某一未知点发生了旋转（比如 样例 1: 样例 2: 你可以假设数组中不存在重复元素。 159. 寻找旋转排序数组中的最小值 标签：sample 情况 panel art 输入 判断 cti 测试数据 bar 原文地址：https://www.cnblogs.com/yunxintryyoubest/p/13191725.html159. 寻找旋转排序数组中的最小值
0 1 2 4 5 6 7 可能变成4 5 6 7 0 1 2）。你需要找到其中最小的元素。样例
输入：[4, 5, 6, 7, 0, 1, 2]
输出：0
解释：
数组中的最小值为0
输入：[2,1]
输出：1
解释：
数组中的最小值为1
注意事项
class Solution:
"""
@param nums: a rotated sorted array
@return: the minimum number in the array
"""
def findMin(self, nums):
# write your code here
start, end = 0, len(nums) - 1
while start + 1 end:
#第一种情况，如果直接是升序数组的话，直接返回
if (nums[start] nums[end]):
return nums[start]
mid = (start + end) // 2
#说明左边是升序的，最小值肯定不在左边，上面已经判断过了
if (nums[start] nums[mid]):
start = mid + 1
else:
#说明右边是升序的，最小值在左边
end = mid
if (nums[start] nums[end]):
return nums[start]
else:
return nums[end]