个人记录-LeetCode 81. Search in Rotated Sorted Array II

问题：
Suppose an array sorted in ascending order 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).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

代码示例：
1、上神器

public class Solution {
    public boolean search(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        return set.contains(target);
    }
}

2、分段讨论
将原来升序数组的后1部份，移动到了前面，可按以下方式2分法处理：

public class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid = -1;

        while(start <= end) {
            mid = (start + end) / 2;

            if (nums[mid] == target) {
                return true;
            }

            //右侧是排序的或左边是未排序的
            if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
                //左侧是排序的或右边是未排序的
            } else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
                if (target < nums[mid] && target >= nums[start]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                //重复部份，++start或--end都可
            } else {
                end--;
            }
        }
        return false;
    }
}