LeetCode-81. 搜索旋转排序数组 II-Java-medium

题目链接

法一（二分）

    /**
     * 二分查找
     * 每次二分，左半部分和右半部分至少有一边是有序的
     *
     * @param nums
     * @param target
     * @return
     */
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] < nums[right]) { // mid落在有序的右半边，则mid的右边都是有序的
                if (target > nums[mid] && target <= nums[right]) { // target落在有序的右半边
                    left = mid + 1;
                } else { // target落在不一定有序的左半边
                    right = mid - 1;
                }
            } else if (nums[mid] > nums[right]) { // mid落在有序的左半边，则mid的左边都是有序的
                if (target >= nums[left] && target < nums[mid]) { // target落在有序的左半边
                    right = mid - 1;
                } else { // target落在不一定有序的右半边
                    left = mid + 1;
                }
            } else {
                right--; // 去重
            }
        }
        return false;
    }
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

本地测试

        /**
         * 81. 搜索旋转排序数组 II
         */
        lay.showTitle(81);
        Solution81 sol81 = new Solution81();
        int[] nums81 = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target81 = 0;
        System.out.println(Arrays.toString(nums81));
        System.out.println(target81);
        System.out.println(sol81.search(nums81, target81));
1
2
3
4
5
6
7
8
9
10