public int search(int[] A, int target) {
		if(A == null || A.length == 0) return -1;
		
		int start = 0, end = A.length - 1, mid;
		while(start <= end) {
		    mid = (end - start) / 2 + start;
		    if(A[mid] == target) return mid;
		    else if(A[start] <= A[mid]) { // should be <= rather than <, as start may == mid
		        if(target < A[mid] && target >= A[start]) end = mid - 1;
		        else start = mid + 1;
		    } else {
		        if(target > A[mid] && target <= A[end]) start = mid + 1;
		        else end = mid - 1;
		    }
		}
		
		return -1;
	}