public static int search2(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] && A[m] >= A[r]) {
				// left sorted, right unsorted
				if (target < A[m] && target >= A[l]) {
					r = m - 1;
				} else {
					l = m + 1;
				}
			} else {
				// right sorted, left unsorted
				if (target <= A[r] && target > A[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			// }else if(A[l] < A[r]){
			// //list sorted
			// if(target < A[m]) r =m -1;
			// else l = m +1;
			// }
		}
		return -1;
	}