public int search(int[] A, int target) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (A.length == 0) {
			return -1;
		}
		int start = 0;
		int end = A.length - 1;
		int mid;
		while (start <= end) {
			mid = (start + end) / 2;
			if (A[mid] == target) {
				return mid;
			}
			if (A[mid] >= A[end]) {// left part sorted
				if (target >= A[start] && target < A[mid]) {
					end = mid - 1;
				} else {
					start = mid + 1;
				}

			} else {// right part sorted
				if (target > A[mid] && target <= A[end]) {
					start = mid + 1;
				} else {
					end = mid - 1;
				}
			}
			System.out.println("Start " + start);
			System.out.println("End " + end);

		}
		return -1;

	}