题目
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1]
输出：0

解法：二分

旋转过后数组分成如上图所示的两段，满足这样的二分性质：第一段>=nums[0]，第二段我们需要找到的就是第二段中的最小值
由于数组中可能存在重复，因此一开始需要先把第二段末尾和第一段开头重复的部分去掉，确保二分性质成立
还需要注意没有旋转的情况
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return -1;
        int n = nums.size() - 1;
        while (n && nums[n] == nums[0]) n--;
        if (nums[n] >= nums[0]) return nums[0];    // 剩下的部分完全单调
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0])
                r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

补充

旋转数组中的查找
旋转数组定义和上面一致，区别在于从最小值变成了查找
可以根据nums[mid]和nums[0], k之间的关系分类讨论
时间复杂度O(logn)，空间复杂度O(1)

// #define SUBMIT
#include <time.h>
#include <iostream>
using namespace std;
const int N = 110;
int a[N];
int main() {
   #ifdef SUBMIT
   freopen("in.txt", "r", stdin);
   freopen("out.txt", "w", stdout);
   long _begin_time = clock();
   #endif
   int n, k;
   cin >> n >> k;
   for (int i = 0; i < n; i++)
      scanf("%d", &a[i]);
   int l = 0, r = n - 1;
   while (l < r) {
      int mid = l + r + 1 >> 1;
      if (a[mid] < a[0]) {
         if (a[mid] <= k && k <= a[n - 1])
            l = mid;
         else
            r = mid - 1;
      }
      else {
         mid = l + r >> 1;
         if (a[mid] >= k && k >= a[0]) {
            r = mid;
         }
         else
            l = mid + 1;
      }
   }
   if (a[l] == k) cout << l;
   else cout << -1;
   #ifdef SUBMIT
   long _end_time = clock();
   printf("\n\ntime = %ld ms", _end_time - _begin_time);
   #endif
   return 0;
}