LeetCode - 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.

因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分4种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

（4）如果A[m]==A[r], 确定不了，那就r--，往下看一步即可。

 

算法的平均时间复杂度为O(logn)。最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

 

public boolean search(int[] A, int target) {
    int l=0, r=A.length-1;
    while(l<=r) {
        int m = (l+r)>>1;
        if(A[m] == target) return true;
        if(A[m]<A[r]) {
            if(target>A[m] && target<=A[r]) {
                l = m+1;
            } else {
                r = m-1;
            }
        } else if(A[m]>A[r]){
            if(target>=A[l] && target<A[m]) {
                r = m-1;
            } else {
                l = m+1;
            }
        } else {
            r--;
        }
    }
    return false;