Friday, October 10, 2014

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


    bool search(int A[], int n, int target) {
        int b = 0;
        int e = n - 1;
        while(b <= e)
        {
            int m = (b + e) / 2;
            if (A[m] == target)
                return true;
   //right part duplicate, and move end backward as the end value could not be the target 
            else if (A[m] == A[e])
                e = e - 1;
   //left part duplicate, and move begin forward as the begin value could not be the target  
            else if (A[m] == A[b])
                b = b + 1;
   //if the right part is still sorted 
            else if (A[m] < A[e])
            {
    //if the target is in the right side range
                if (target > A[m] && target <= A[e])
                    b = m + 1;
                else
                    e = m - 1;
            }
   //left part must be sorted 
            else
            {
    //if the target is in the left side range
                if (target < A[m] && target >= A[b])
                    e = m - 1;
                else
                    b = m + 1;                
            }
        }
        
        return false;
    }

No comments:

Post a Comment