Leetcode--Java--81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

去重 + 二分法

1. 本题与该系列第一题几乎一样，只不过多了个去重。点这里，不再赘述。

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) return false;
        int R = nums.length - 1;
        //首先去重，将第二段与第一段重复的部分删掉
        while (R >= 0 && nums[R] == nums[0]) R --;
        //如果全删完了，说明数组全部相同 直接比较是否等于target
        if (R < 0) return nums[0] == target; 
        //下面为两次二分  与系列一完全一样
        int l = 0, r = R;
        while (l < r) {
            int mid = l + r + 1>> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        //确定target所在的区间是第一段还是第二段
        if (target >= nums[0]) {
            r = l;
            l = 0;
        } else {
            l ++;
            //注意此时不是数组的边界了，而是去重后的边界
            r = R;
        }
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1; 
        }
        return nums[r] == target;

    }
}