旋转数组具有重复项时，需要去除有些末尾元素，才能满足二分的二段性：$左半段 > nums.back(),右半段 <= nums.back()$

153. 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        /*
            最小的元素 必然满足 nums[i] <= nums.back(),根据这个二分
        */
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

154. 寻找旋转排序数组中的最小值 II

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r && nums[r] == nums[0]) r -- ; // 删除重复元素 转换为第一题
        // 记录删除后末尾元素的值
        int end = nums[r];
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] <= end) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(nums[mid] > nums[0]) l = mid;
            else r = mid - 1;
        }

        if(target >= nums[0]) l = 0;
        else l = r + 1,r = n - 1;

        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if(nums[r] != target) return -1;
        return r;
    }
};

81. 搜索旋转排序数组 II

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0,r = nums.size() - 1;
        while(l <r && nums[r] == nums[0]) r --;
        // 记录删除后的末尾元素和下标
        int end = nums[r];
        int tr = r;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] <= end) r = mid;
            else l = mid + 1;
        }
        if(target <= end) r = tr;
        else l = 0, r --;   // 同样可能溢出，下面用l。当nums[]只有一个元素，r--溢出

        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        } 
        if(nums[l] != target) return false;
        return true;
    }
};