public static boolean searchDup(int[] A, int target) {
        // write your code here
    	int start = 0, end = A.length - 1;
    	while(start <= end){
    		int mid = (start + end)/2;
    		if(A[mid] == target)
    			return true;
    		if(A[start] < A[mid]){
    			//the left side is sorted
    			if(A[start] <= target && target < A[mid]){
    				//target in the left side
    				end = mid;
    			}else{
    				start = mid + 1;
    			}
    		}else if(A[mid] < A[end]){
    			//right side is sorted
    			if(A[mid] < target && target <= A[end]){
    				//in the right side
    				start = mid + 1;
    			}else{
    				end = mid;
    			}
    		}else{
    			if (A[start] == target) {
					return true;
				}
    			start ++;
    		}
    	}
    	return false;
    }