LeetCode(81) -- Search in Rotated Sorted Array II

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

The Best Solution

class Solution {
    public boolean search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] == nums[l]) {
                l++;
            } else if (nums[mid] > nums[l]) {
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

这个版本是对比了几个答案后找到的思路最清晰的写法了。这道题需要注意的点是，数字可能重复，这就导致第一个数和最后一个数可能一样，找到中间点后，我们就不容易区分左右了。

解法办法是，总体思路依然是用中间点跟最左边的值进行比较，从而确定中间点在单调增区间还是在有gap的那个区间。重点是，这次我们如果发现左边的值跟中间点相等，就把左边界向右移动一格。排除中间点跟左边界相等的可能性之后，如果中间点大于左边界，那么中间点必然在左边的那个上升区间，下一步就能判断target到底是在中间点的左边还是右边了。同理，如果小于左边界，那么它必然在右半边较矮的上升区间，同样也可以判断了。

判断时我们可以把这道题理解为根据y值确定x值。