搜索旋转排序数组2

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

( 例如，数组 [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
示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:

这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
通过次数45,330提交次数125,327

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定的是无序的，先划分，一部分是有序的进行二分查找，一部分是无序的继续划分

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length > 0) {
            return divideAndSearch(nums, target, 0, nums.length - 1);
        } else {
            return false;
        }
    }

    public boolean divideAndSearch(int[] nums, int target, int start, int end) {
        if (end - start <= 1) {
            if (nums[start] == target || nums[end] == target) {
                return true;
            } else {
                return false;
            }
        }
        if (nums[end] > nums[start]) {//给定的是有序的
            if (nums[end] >= target && nums[start] <= target) {//target的大小在中间
                int left = start, right = end;
                while (left <= right) {
                    int mid = left + (right - left) / 2;    //防止溢位
                    if (nums[mid] > target)
                        right = mid - 1;
                    else if (nums[mid] < target)
                        left = mid + 1;
                    else {
                        return true;
                    }
                }
            }

        } else {//给定的是无序的，先划分，一部分是有序的进行二分查找，一部分是无序的继续划分
            int left = start, right = end, mid = (left + right) / 2;
            boolean flag1 = divideAndSearch(nums, target, left, mid);
            boolean flag2 = divideAndSearch(nums, target, mid, right);
            if (flag1 || flag2) {
                return true;
            }
        }
        return false;
    }
}

不划分方法

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;
            else if(nums[mid]<nums[r]){//右半部分是有序的
                if(nums[mid]<target && target<=nums[r])l=mid+1;
                else r=mid-1;
            }
            else if(nums[mid]>nums[r]){//左半部分是有序的
                if(nums[mid]>target && target>=nums[l])r=mid-1;
                else l=mid+1;
            }
            else r--;//从右向左移动
        }
        return false;
    }
}

参考文献

我不会dp的题解

赏

谢谢你请我吃糖果

微信