public static int search(int[] A, int target) {
		// write your code here
		int t=target;
		int l=0, r=A.length-1;
		while (l<=r) {
			int m=l+(r-l)/2;
			if (A[m]==t)
				return m;
			if (A[l]<=A[m]) {
				if (A[l]<=t&&t<A[m]) {
					r=m-1;
				} else {
					l=m+1;
				}
			} else {
				if (A[m]<t&&t<=A[r]) {
					l=m+1;   
				} else {
					r=m-1;
				}
			}
		}
		return -1;
	}