首页 > 代码库 > leetcode第一刷_Search in Rotated Sorted Array II

leetcode第一刷_Search in Rotated Sorted Array II

接着上一篇,同样是旋转数组中查找问题。如果这个数组有重复元素怎么办呢?会有什么影响?

我举一个极端的例子,假设数组中的元素是这样的,1,1,2,1,1,1,1,我们要在这个数组中查找2,一开始的A[middle]=1,发现比target小,那我们就看看A[0]和A[N],发现都跟A[middle]相等,那么这个2到底在哪一半中?只有上帝知道,如果他老人家真的存在的话。这种时候我们怎么办呢?没有其他的办法,只能从头开始乖乖的扫描,直到发现target或者确定他不存在。

为什么会出现这种情况,或者说包含重复元素跟不包含重复元素在本质上有什么区别呢?这种区别又是怎样影响复杂度的呢?我觉得区别在于,当A[middle]与两头的元素相等时,我们没法找到一半有序的元素,因此我们也就没法通过比较边界来确定target在不在这一半元素之中,也就是我们在每一轮的判定中,无法确定的扔掉一半元素,最坏情况下的复杂度自然就提高到了O(N)。

编码上没有太大的区别,只要当与两头元素都相等时,就只移动左边的指针,逐个扫描过来,需要注意的是,每次移动时要判定这个值是否跟target的相等。

class Solution {
public:
    bool search(int A[], int n, int target) {
        int l = 0, r = n-1, mid;
        while(l<=r){
            mid = (l+r)/2;
            if(A[mid] == target)    return true;
            if(A[l]<A[mid]){
                if(target>=A[l]&&target<A[mid])
                    r = mid-1;
                else
                    l = mid+1;
            }else if(A[mid]<A[r]){
                if(target>A[mid]&&target<=A[r])
                    l = mid+1;
                else
                    r = mid-1;
            }else{
                if(A[l] == target)  return true;
                else    l++;
            }
        }
        return false;
    }
};