LeetCode 第 154 题：“寻找旋转排序数组中的最小值 II”题解
题解地址：二分法 + 分治法（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5] 输出: 1 示例 2：
输入: [2,2,2,0,1] 输出: 0 说明：
这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
二分法 + 分治法（Python 代码、Java 代码）
方法一：二分法
只要是一次可以排除一半，都可以用二分法。那么如何使用二分法呢？我们很自然会想到使用边界的值和中间位置的值进行比较。
注意：我这里说的是中间数，即位于中间的那个数，不是中位数，请读者注意区分。
于是可以分为以下两种情况：
1、左边界与中间数比较
我们在纸上写出几个例子：
例 1：[1, 2, 3, 4, 5]
例 2：[2, 3, 4, 5, 1]
以上这两个例子，中间数都比左边界大，但是旋转排序数组的最小值可能在中间数的左边（例 1），也可能在中间数的右边（例 2），因此不能使用左边界与中间数比较作为二分法的讨论依据。
接下来，看看另一种讨论依据。
2、右边界与中间数进行比较：
（1）当中间数比右边界表示的数大的时候，中间数就一定不是目标数（旋转排序数组的最小值），举个例子：
例 3：[7, 8, 9, 10, 11, 12, 1, 2, 3]
中间数 11 比右边界 3 大，因此中间数以及中间数前面的数都不是目标数，把左边界设置中间数位置 + 1，即 l = mid + 1；
（2）当中间数比右边界表示的数小的时候，中间数就可能是目标数（旋转排序数组的最小值），举个例子：
例 4：[7,8,1,2,3]
中间数 1 比右边界表示的数大的时候，说明，中间数到右边界是递增的（对于这道题是非递减），那么中间数右边的（不包括中间数）就一定不是目标数，把它们排除，因此，把右边界设置为 r = mid。
（3）当中间数与右边界表示的数相等的时候，看下面两个例子：
例 5：[0, 1, 1, 1, 1, 1, 1]
例 6：[1, 1, 1, 1, 0, 1, 1]
目标值可能在中间数的左边，也可能在中间数的右边，那么怎么办呢？很简单，此时你看到的是右边界，就把只右边界排除掉就好了。这正是因为右边界和中间数相等，你去掉了右边界，中间数还在，就让中间数在后面的循环中被发现吧。
因此，根据中间数和末尾数的大小关系，可以使用二分法找到目标值。
关键：解本题的关键在于举例，考虑到不同的情况。
以下代码是根据我在刷题过程中总结出来的最好用的二分法模板写成。我专门把这个二分法模板好用的地方、使用它的技巧和注意事项整理在了「力扣 」第 35 题：搜索插入位置的题解《特别好用的二分查找法模板（Python 代码、Java 代码）》，希望能对大家有所帮助。
参考代码 1：
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return Exception('程序出错')
left = 0
right = size - 1
while left < right:
# mid = left + (right - left) // 2
mid = (left + right) >> 1
if nums[mid] > nums[right]:
# mid 肯定不是最小值
# [7,8,9,10,11,1,2,3]
left = mid + 1
elif nums[mid] < nums[right]:
# mid 有可能是最小值
# [7,8,1,2,3]
right = mid
else:
# 都有可能，所以就把 right 排除了
# [1,1,1,1,1,0,1]
assert nums[mid] == nums[right]
right = right - 1
# 无需后处理
return nums[left]
public class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len - 1;
while (left < right) {
// int mid = left + (right - left) / 2;
int mid = (left + right) >>> 1;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
assert nums[mid] == nums[right];
right--;
}
}
return nums[left];
}
}
方法二：分治法
代码同 LeetCode 第 153 题。
分治法将原问题划分成若干与原问题同结构且规模更小的子问题，等到这些子问题解决了以后，原问题也得到了解决。
参考代码 2：
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
raise Exception('程序出错')
if size == 1:
return nums[0]
return self.__find_min(nums, 0, size - 1)
def __find_min(self, nums, left, right):
if left == right:
return nums[left]
if left + 1 == right:
return min(nums[left], nums[right])
# mid = left + (right - left) // 2
mid = (left + right) >> 1
return min(self.__find_min(nums, left, mid), self.__find_min(nums, mid + 1, right))
public class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if (len == 0) {
throw new IllegalArgumentException("数组为空，最小值不存在");
}
return findMin(nums, 0, len - 1);
}
private int findMin(int[] nums, int left, int right) {
if (left + 1 >= right) {
return Math.min(nums[left], nums[right]);
}
if (nums[left] < nums[right]) {
return nums[left];
}
// int mid = left + (right - left) / 2;
int mid = (left + right) >>> 1;
return Math.min(findMin(nums, left, mid - 1), findMin(nums, mid, right));
}
}