public static int search_modify(int[] A, int target) {
    	int start = 0, end = A.length - 1;
    	while (start + 1 < end) {
			int mid = start + (end - start) / 2;
			if (A[mid] == target) {
				return mid;
			}
			
			if (A[start] < A[mid]) {
				// A[start..end] is sorted
				if (A[start] <= target && target < A[mid]) {
					//in the sorted part;
					end = mid;
				} else {
					//in the unsorted part
					start = mid;
				}
			} else {
				// A[mid..end] is sorted
				if (A[mid] < target && target <= A[end]) {
					//in the sorted part
					start = mid;
				} else {
					// in the unsorted part
					end = mid;
				}
			}
		}
    	if (A[start] == target) {
			return start;
		}
    	if (A[end] == target) {
			return end;
		}
    	return -1;
    }