2014年4月20日 星期日

[LeetCode] Search in Rotated Sorted Array II

Problem:
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.
Solution:O(logn)
public class Solution {
    public boolean search(int[] A, int target) {
        if(A == null || A.length == 0)
            return false;
        return doSearch(0,A.length-1,A,target);
    }
    
    public boolean doSearch(int start, int end, int[] A, int target){
        if(end< start || (end == start && A[start]!=target ))
            return false;
            
        int m = (start+end)/2;
        if(A[m] == target)
            return true;
        
        if(A[m] < A[start]){
            if(A[m] <= target && target <=A[end])
                return doSearch(m+1,end,A,target);
            else
                return doSearch(start,m-1,A,target);
        }    
        else if(A[m] > A[start]){
            if(A[m] >= target && target >=A[start])
                return doSearch(start,m-1,A,target);
            else
                return doSearch(m+1,end,A,target);
        }
        else if(A[m] == A[start]){
            if(A[m] != A[end])
                return doSearch(m+1,end,A,target); 
            else 
                return doSearch(start,m-1,A,target) || doSearch(m+1,end,A,target);
        }
        return false;   
    }
}
Key Concept:always do binary search in correct session.

沒有留言:

張貼留言