1.题目基本信息
1.1.题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
- 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
1.2.题目地址
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/
2.解题方法
2.1.解题思路
二分查找（红蓝染色法）
2.2.解题步骤
第一步，确定红蓝染色的两个特征。不变特征：1.红色始终标记在小于target的指针位置（target这里为目标求的最小索引），蓝色始终标记大于等于target的指针位置；2.左闭右闭，left-1始终指向红色，right始终指向蓝色（这里和普通的二分情况有所不同，right从一开始就属于蓝色阵营）
第二步，使用左闭右闭区间的模板处理。mid取中位数的下位整数，如果mid指向的值大于right指向的值，mid一定小于target，标记mid处为红色，即left更新为mid+1。如果小于right指向的值，则一定在右非递减区间，但是这里的right不能更新为mid-1，因为mid-1可能是红色区域，但是right不能指向红色区域，所以将right更新mid处。如果right和mid处值相等，此时mid可能是红色区域也可能是蓝色区域，所以right自减1是最保险的策略。最后直到left大于right退出循环。
第三步，经过上面的循环，由于left-1指向最后一个红色位置的特征，所以left一定指向target，返回nums[left]即为最终结果。
注意：这里如果nums[mid] < nums[right]的情况不好处理，可以去掉这一步的判断，在nums[mid] <= mid[right]时，直接right自减1，一样能AC，且结果差不了多少。这种做法可以参考下面的C++代码。
3.解题代码
Python代码
class Solution:
# 特点：right处的值在右边的非递减区间总是最大的，但是比左边的非递减区间的值都要小。根据这个特征就可以进行二分法求解。
# 第一步，确定红蓝染色的两个特征。不变特征：1.红色始终标记在小于target的指针位置（target这里为目标求的最小索引），蓝色始终标记大于等于target的指针位置；2.左闭右闭，left-1始终指向红色，right始终指向蓝色（这里和普通的二分情况有所不同，right从一开始就属于蓝色阵营）
# 第二步，使用左闭右闭区间的模板处理。mid取中位数的下位整数，如果mid指向的值大于right指向的值，mid一定小于target，标记mid处为红色，即left更新为mid+1。如果小于right指向的值，则一定在右非递减区间，但是这里的right不能更新为mid-1，因为mid-1可能是红色区域，但是right不能指向红色区域，所以将right更新mid处。如果right和mid处值相等，此时mid可能是红色区域也可能是蓝色区域，所以right自减1是最保险的策略。最后直到left大于right退出循环。
# 第三步，经过上面的循环，由于left-1指向最后一个红色位置的特征，所以left一定指向target，返回nums[left]即为最终结果。
# 注意：这里如果nums[mid]<nums[right]的情况不好处理，可以去掉这一步的判断，在nums[mid]<=mid[right]时，直接right自减1，一样能AC，且结果差不了多少。
def findMin(self, nums: List[int]) -> int:
left,right=0,len(nums)-1
while left<=right:
mid=(right-left)//2+left
if nums[mid]>nums[right]:
left=mid+1
elif nums[mid]<nums[right]:
right=mid # mid-1可能会跳到左非递减区间，所以不可以
else: # 相等的时候不能盲目二分，mid可能是红色阵营也可能是蓝色阵营，所以让right自减1即可
right-=1
return nums[left]
C++代码
class Solution {
public:
int findMin(vector<int>& nums) {
int length=nums.size();
int left=0,right=length-1;
while(left<right){
int mid=(right-left)/2+left;
if(nums[mid]>nums[right]){
left=mid+1;
}else{
right--;
}
}
return nums[left];
}
};
4.执行结果
