from CodeTop, Leetcode, 154. 寻找旋转排序数组中的最小值 II。
二分查找。
题意：
已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
理解：
不管旋转多少次，旋转结束后的数组一定是由两段（其中一段的长度可能是零，这样就退化为了一段）分别升序的子区间组成，且第二段的最大值（最右侧）一定小于等于第一段的最小值（最左侧），这样把两段先右后左拼起来才是一个完整升序的序列。
但是这个题，难度在于，由于存在重复元素，且旋转点可能正好是重复的元素。旋转后，第二段升序区间的右侧和第一段的左侧可能是相等的，而且可能是连续好几个元素相等，如下图所示：
这就会对我们寻找分界点元素，也就是大于等于 nums[0] 的最后一个元素产生干扰。比如，你寻找的区间可能根本就不在第一个升序段。于是要更加深入理解二分算法的“在限定区间内寻找满足特定性质的元素”之本质，性质还是那个性质：大于等于 nums[0] 的最后一个元素之前，但区间要变一下。闭区间（左）右端点需要收缩到不包含重复元素的地方，也就是上图水平线段和斜线段的交界位置。
相应地，对二分终点是否在右侧端点的判断也不能用 num.size()-1，而应当记录一下最初收缩端点时候的右端点位置。
代码：
先进性区间两段重复元素过滤，然后直接背二分模板。
int l = 0, r = nums.size()-1;
while(l + 1 < nums.size() && nums[l] == nums[l+1]) l ++;
while(r - 1 >= 0 && nums[r] == nums[r-1]) r --;
int r_bound = r;
while(l < r){
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if (r == r_bound) return nums[0];
return nums[r+1];
