题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
思路
总体二分:
- if mid大于high, low = mid + 1
- if mid小于high, high = mid
- 直到mid=high,取此位置的数
class Solution(object):
def minArray(self, numbers):
low, high = 0, len(numbers) - 1
while low < high:
mid = (high+low) / 2
if numbers[mid] > numbers[high]:
low = mid + 1
elif numbers[mid] < numbers[high]:
high = mid
else:
if (numbers[high - 1] > numbers[high]): # 确保正确的下标
low = high
break
high -= 1 # 如果numbers[hign-1]=numbers[high]的情况
return numbers[low]