public static int search(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 mid;
    		}
    		
    		if(A[start] <= A[mid]){
    			//left side is sorted
    			if(A[start] <= target && target < A[mid]){
    				//target in the left side
    				end = mid;
    			}else{
    				//target in the right side
    				start = mid + 1;
    			}
    		}else{
    			//the right side is sorted, since there is no duplicate
    			if(A[mid] < target && target <= A[end]){
    				//in the right side
    				start = mid + 1;
    			}else{
    				end = mid;
    			}
    		}
    	}
    	return -1;
    }