Wednesday, July 22, 2015

LintCode (63) Search in Rotated Array II

Search in Rotated Sorted Array II

40%
Accepted
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.


和find min in rotated array with dup是一样的,如果有dup,判断左旋和右旋无法判断的时候,移动beg,这样,最差复杂度为o(n)


 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
33
34
35
36
37
class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &A, int target) {
        // write your code here
        if (A.empty())
            return false;
        int beg=0; 
        int end=A.size()-1;
        while(beg+1<end){
            int mid=beg+(end-beg)/2;
            if (A[mid]==target)
                return true;
            if (A[mid]>A[beg]){
                if (A[mid]>=target && target>=A[beg]){
                    end=mid-1;
                } else{
                    beg=mid+1;
                }
            } else if (A[mid]<A[beg]){
                if (A[mid]<=target && target<=A[end]){
                    beg=mid+1;
                } else{
                    end=mid-1;
                }
            } else{
                beg++;
            }
        }
        return (A[beg]==target || A[end]==target);
    }
    
};

No comments:

Post a Comment