public static int search3(int[] A, int target) {
		if (A.length == 0)
			return -1;
		int l = 0;
		int r = A.length - 1;
		int m;
		while (l <= r) {
			m = (l + r) / 2;
			if (target == A[m]) {
				return m;
			} else if (A[l] <= A[m]) {
				// left sorted
				if (target < A[m] && target >= A[l]) {
					r = m - 1;
				} else {
					l = m + 1;
				}
			} else {
				// right sorted
				if (target <= A[r] && target > A[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
		}
		return -1;
	}