Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

 

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

Naive Way: 在原来的基础上增加了数字可重复的条件。这一条件带来什么影响，会不会影响算法复杂度。这种时候我发现一个比较高明的方法是考虑最坏的情况。

这是是 Search in Rotated Sorted Array I 的代码。算法复杂度是O(logn)。

public class Solution {
    public int search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private int search(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return middle;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    }
}

如果有重复，最坏的情况是全是同一个数，比如

[1  1  1  1  1]

这样只有1可以做target，找的时候第一下就返回了，不能说明情况。那么退一步只有一个数是不重复的

[1  1  1  2  1  1]

这时有一个重大发现就是这个2摆在哪里都可以，都是rotated array。如果2摆在最前面

[2  1  1  1  1  1]

经过原来的方法会二分的执行算法直到找到2在Index=0的位置。如果2摆在最后，可想而知也会符合O(logn)的时间的。最后把2摆在中间。

[1  1  1  2  1  1]

问题来了，会出现b1 == e1 == b2 == e2的情况。对于这种情况，是无法正确找出2的半区的，因为2既有可能在前半部分，也有可能在后半部分。

这是否说明第一次的算法在这里不能用了呢。仔细走一遍第一次的算法，到了选择分区时：

if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                // 搜索前半部分
            else
                //搜索后半部分
        }else{
            if(A[middle] < target && A[end] >= target)
                //搜索后半部分
            else
                //搜索前半部分
        }

第一个选择条件A[middle] > A[end]不成立，第二个选择条件A[middle] < target && A[end] >= target也不成立，就会自动进入搜索前半部分。这时会想如果能去除一头一尾的重复部分呢？
这样原数组就会变成[1 2 1]，此时过一遍算法发现是可以正确找到2的。那么一个假设诞生了：每次都先去除一头一尾的重复部分，再运行算法是否就可以了呢? 经过测试是可以的，并且因为去除一头一尾的意义其实是打破b1==e1==b2==e2的平衡性，任意去除尾部或者头部都可以打破这种平衡，使数组重心改变，一旦数组重心改变，原来的算法其实就是正确的找出下一个半区。

此时算法复杂度变为O(n)。

public class Solution {
    public boolean search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private boolean search(int[] A, int begin, int end, int target){
        while(begin+1 < end){
            if(A[begin+1]!=A[begin])
                break;
            begin++;
        }
        if(begin > end)
            return false;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return true;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    } 
}

总结一下，就是Binary search这种算法的核心思想是利用O(1)的时间发现左右半区的不平衡性，从而发现决定focus on哪一个半区，所以一旦有可能出现完全平衡的情况，binary search就无法正确运行，此时可能是目标情况，也可能是边缘情况，创造新的不平衡性可使算法运行下去。

类似binary search的题目还有Search-in-rotated-sorted-array, Search-insert-position