题目:
思路:
关于旋转数组有各种变种问题：是否有重复元素、寻找最大值最小值、寻找旋转点下标(旋转点的值等于最小值)、查找给定元素。本题就是对有重复元素的旋转数组，寻找其最小值。
首先想到二分查找没问题，关键在于怎么通过判断middle元素的相对大小去逐渐缩小搜索区间。如下图所示(无重复元素)
-
循环二分，middle = (left + right) // 2(向下取整)为每次二分的中点，恒有left <= middle < right
- 当num[middle] < num[right]，middle处于右边序列，旋转点一定在[left, middle]闭区间内，因此执行right = middle(不是middle-1，因为middle有可能是旋转点)
- 当num[middle] > num[right]，middle处于左边序列，旋转点一定在[middle+1, right]闭区间内，因此执行left = middle+1(middle肯定不是旋转点)
- 当num[middle] = num[right]，无法判断middle处于哪边序列，执行right = right-1，证明该操作的正确性只需证明操作后旋转点仍然在[left, right]区间内即可
- 若middle在右边序列，则[middle, right]区间内所有元素相等，执行right = right-1只会抛弃一个重复值，旋转点仍然在[left, right]区间
- 若middle在左边序列，由于左边序列任一元素 >= 右边序列任一元素，因此可推出旋转点num[x] <= num[right] = numb[middle]，并且[left, middle]区间内所有元素相等
- 若num[x] < num[right]，则right左边仍有更小的元素(最小值位于左边序列)，执行right = right-1之后，旋转点仍然在[left, right]区间
- 若num[x] = num[right]，则左边序列所有元素相等，并且等于[left, middle]区间内的元素
- 若right > x，执行right = right-1后，旋转点仍然在[left, right]区间
- 若right = x，执行right = right-1后，旋转点不在区间内，但返回的num[0]仍然是最小值。因为之后的二分循环一直在执行right = middle，而区间[left, middle]内的元素值一定都等于旋转点的值也就是最小值
-
返回值，当left = right时跳出循环，返回num[left]即可
-
特殊情形
- [1, 0, 1, 1, 1]，middle = 2在右边序列
- [1, 1, 1, 0, 1]，middle = 2在左边序列
- [1, 1, 1, 2, 3, 1]，跳过旋转点，返回num[0]
- [1, 2, 3, 4, 5]，可以认为从头到尾全部旋转，寻找最大值时相当于右边序列为空，寻找最小值时相当于左边序列为空
-
寻找最小值时不可以让num[middle]和num[left]进行对比，因为对比的目的是判断middle处于哪边序列，当只有一个序列时会出现问题。寻找最大值时和num[left]比较，寻找最小值时和num[right]比较。
-
误区: 判断middle处于哪边序列中时，只需要和一边比较就可以，不需要同时比较left和right。从结果上看其实并不需要很复杂很多的判断条件，一开始判断条件过多容易混乱，需要从多种条件中抽离出关键点。
代码:
Python
class Solution(object):
def minArray(self, numbers):
"""
:type numbers: List[int]
:rtype: int
"""
left = 0
right = len(numbers) - 1
while left < right:
middle = (left + right) // 2
if numbers[middle] > numbers[right]:
left = middle + 1
elif numbers[middle] < numbers[right]:
right = middle
else:
right = right - 1
return numbers[left]