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
class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[left] || target == nums[right] || target == nums[mid]) {
                return true;
            }
            if ((nums[mid] < nums[left] && target < nums[left]) || (nums[mid] > nums[left] && target > nums[left])) {
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                while (left < right && nums[left] == nums[left + 1])
                    left += 1;
                while (left < right && nums[right] == nums[right - 1])
                    right -= 1;
                left += 1;
                right -= 1;
            }
        }
        return false;
    }
}

这道题和之前的那个版本1没有重复元素的区别在于, 有时候我们不能排除某个部分的数字. 如果nums[mid]和target都是小于nums[left]或者都是大于nums[left]那么它俩一定处于一个部分(左半部分或者右半部分), 此时就是正常的binary search的过程. 但是如果出现一个小于一个大于或等于或者一个大于另一个小于或等于的情况的时候, 这就非常多的情况了. 比较聪明的做法就是先判断target是否和nums[left]以及nums[mid]相等, 如果相等直接齐活了. 如果都不相等,
那么此时我们就知道target一定是要么大于nums[left], 要么小于nums[left]. 如果target大于nums[left]那么此时nums[mid]就是小于或者等于nums[left];
如果target小于nums[left], 那么nums[mid]就是大于或者等于nums[left]. 让人头疼的就是nums[mid]等于nums[left], 此时无法排除某一部分. 但我们知道的是target一定不等于left, 于是left可以往里面缩了. 我们可以同时再进一步, 让target也和nums[right]比较, 如果不相等, right也能往里面缩.

以上就是大概的思路.

为什么while循环后面还跟着left += 1和right -= 1. 因此两个while循环停止的时候, left和right处在的位置指向的值还和while循环前指向的值一样(尽管位置可能不同了). 于是我们还要手动再缩一格.

时间复杂度: O(n) 比如都是一样的数字但是target不在array中出现过.
空间复杂度: O(1)

下面的答案是我收到它的启发才写出了上面的答案.

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
class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = end + (start - end) / 2;
            // Do 3 comparisons
            if (nums[mid] == target || nums[start] == target || nums[end] == target) {
                return true;
            }

            if (target > nums[mid] && target < nums[end]) {
                // target on right
                start = mid + 1;
                continue;
            } else if (target < nums[mid] && target > nums[start]) {
                // target on left
                end = mid - 1;
                continue;
            }
            // Equal case
            ++start;
            --end;
        }

        return false;
    }
}