学步园

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.

Java Solution (
refer to my blog
LeetCode Solutions : Search in Rotated Sorted Array ):

public class Solution {
    public boolean search(int[] A, int target) {
		if(A.length==0)
			return false;
        int low=0;
		int high=A.length-1;
		while(low<=high){
			int mid=low+(high-low)/2;
			if(target==A[mid])
				return true;
			if(A[low]<A[mid]){// the elements from low to mid is strictly increasing order
				if(A[low]<=target&&target<A[mid])
					high=mid-1;
				else
					low=mid+1;
			}else if(A[low]>A[mid]){// the elements from mid to high is strictly increasing order 
				if(A[mid]<target&&target<=A[high])
					low=mid+1;
				else
					high=mid-1;
			}
			else // skip the duplicate one,that is to say,A[low] == A[mid]
				low++;
		}
		return false;		
    }
}

Of course, you are able to resolve it with the brute one, also need O(n)