搜索旋转排序数组II

来源Leetcode第81题搜索旋转排序数组II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

不正经解法

在做题的时候想到是不是可以用库函数来解决，想到String类里有方法indexOf(char)，但是在提交时失败了，因为所要查找的target可能是2位数及其以上，于是改用contains.(Integer.toString(target)) ,在倒数第二个测试用例时出错了。
经过排查发现，target是4764，而在nums里有-4764，转化为String之后调用contains自然而然的就会返回true了。
还是不死心，在Array类的方法里看到有Arrays.binarySearch这个函数，最终成功解决了，但是提交时用时才打败了23.52%的用户，按理而言时间复杂度不应该这么高才对。
代码如下：

Arrays.sort(nums);
return Arrays.binarySearch(nums,target) > -1;

二分查找

与33题不同的是，这题允许数据重复，因而当有重复数字，会存在A[mid] = A[end]的情况。此时右半序列A[mid-1 : end]可能是sorted，也可能并没有sorted，所以当A[mid] = A[end] != target时，无法排除一半的序列，而只能排除掉A[end]，搜寻A[start : end-1]

public boolean search(int[] nums, int target) {
    int len = nums.length,left = 0,right = len - 1;
    while (left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] == target) return true;
        if(nums[mid] < nums[right]){
            if(nums[mid] < target && nums[right] >= target)
                left = mid + 1;
            else right = mid - 1;
        }else if (nums[mid] > nums[right]){
            //此时是在发生了旋转的区域
            //如果中间的数小于最右边的数，则右半段是有序的，
            //如果中间数大于最右边数，则左半段是有序的，
            //我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，
            //这样就可以确定保留哪半边了，
            if(nums[left] <= target && nums[mid] > target)
                right = mid - 1;
            else left = mid + 1;
        }else right-- ;
    }
    return false;
}

按照题解的，稍微的改了一下

public boolean search(int[] nums, int target) {
    int len = nums.length,left = 0,right = len - 1;
    if(len == 0) return false;
    while (left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] == target) return true;
        if(nums[mid] < nums[right]){
            if(nums[mid] < target && nums[right] >= target)
                left = mid + 1;
            else right = mid - 1;
        }else if (nums[mid] > nums[right]){
            //此时是在发生了旋转的区域
            //如果中间的数小于最右边的数，则右半段是有序的，
            //如果中间数大于最右边数，则左半段是有序的，
            //我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，
            //这样就可以确定保留哪半边了，
            if(nums[left] <= target && nums[mid] > target)
                right = mid - 1;
            else left = mid + 1;
        }else {
            if(nums[left] == target)
                return true;
            else right-- ;
        }
    }
    return nums[left] == target;
    //夹逼以后，还要判断一下，是不是 target
}