【Leetcode】81.搜索旋转排序数组 II

81 搜索旋转排序数组 II

和上面一道题相似，只是允许在数组中可以出现重复元素

思路：先找到旋转点，然后看是需要在哪一边进行二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    public boolean search(int[] nums, int target) {
        if(nums.length < 1)
            return false;
        if(nums.length == 1)
            return nums[0] == target ? true : false;
        //原排序数组是升序，旋转后的数组打破了这个升序。
        //即有且只有一个位置，其右边元素小于它，破坏了升序。先把这个位置找到，记为index
        int index = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < nums[i - 1])
                index = i - 1;
        }
        //index左边和右边分别为两个升序数组，先判断target在哪个数组中，再在其中进行二分查找
        if(nums[0] <= target && target <= nums[index])
            return binsearch(nums, 0, index, target);
        if(target >= nums[index + 1] && target <= nums[nums.length - 1])
            return binsearch(nums, index + 1,nums.length - 1,target);
        return false;
    }

    //此函数在数组nums中从left到right的位置上对target进行二分查找
    public boolean binsearch(int[] nums, int left, int right, int target){
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target == nums[mid])
                return true;
            else if(target > nums[mid])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
}