1. 无重复
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
思路：这个是找最小，和找指定数字其实差不多的。画个示意图吧
二分查找，关键是扔掉不包含最小值的那一半。
1.如果右半部分满足 n[m] < n[r] 则右半部分是递增的， 让 r = m 因为m位置有可能是最小的，把递增的那半扔掉。
2.否则，左边是递增的，直接让 l = m + 1 因为m处比原本的 l 大，不可能是最小值。
如果这个序列是顺序的，会归为情况1. 如果右半部分不是递增的则 大|小 的部分一定在右边，最小值不会在左边区域。
最后l = r 时 就是最小值位置。
优化版代码：
int findMin(vector<int> &num) {
int lo =, hi = num.size()-;
while(lo<hi){
int mid = lo + (hi - lo) / ;
if(num[mid]>num[hi]) lo=mid+;
else hi=mid;
}
return num[lo];
}
我的原版代码：
int findMin(vector<int> &num) {
int l = , r = num.size() - ;
while(l <= r)
{
if(l == r) return num[l];
int m = (l + r) / ;
if(num[r] > num[m]) //右边是上升区
{
r = m;
}
else
{
l = m + ;
}
}
}
2. 有重复
原本的有序数列是这样的，我们只展现一段相同数字，多段相同数字是同理的。
1. 如果n[m] < n[r] , 那么右半部分是递增的，处理跟无重复数字一样 r = m;
2. 如果n[m] > n[r] , 说明 大|小 的衔接处在右边，扔掉左边 l = m + 1;
3. 如果n[m] == n[r] 有几种可能
这时，我们跳过复杂的判断，直接让 r-- 再进行下一次判断。 如果所有数字都一样的话，最坏的计算复杂度为O（n）
int findMinDuplicates(vector<int> &num) {
int l = , r = num.size() - ;
while(l < r)
{
int m = l + (r - l) / ;
if(num[r] > num[m]) //右边是上升区
{
r = m;
}
else if(num[r] == num[m])
{
r--;
}
else
{
l = m + ;
}
}
return num[l];
}