public int search1(int[] A, int target) {
		if (A.length < 1)
			return -1;
		int left = 0, right = A.length - 1;
		while (left <= right) {
			int middle = (right + left) / 2;
			if (A[middle] == target)
				return middle;
			// the left part was sorted
			if (A[left] <= A[middle]) {
				if (A[left] <= target && A[middle] > target) {
					right = middle - 1;
				} else {
					left = middle + 1;
				}
				// in the observation, the right part was always sorted
			} else {
				if (target >= A[middle + 1] && target <= A[right])
					left = middle + 1;
				else {
					right = middle - 1;
				}
			}

		}
		return -1;
	}