public static int searchInsert_modify(int[] A, int target) {
    	int start = 0, end = A.length - 1;
    	if (target < A[0]) {
			return 0;
		}
    	if (target > A[end]) {
			return end + 1;
		}
    	while (start + 1 < end) {
			int mid = start + (end - start)/2;
			if (A[mid] == target) {
				return mid;
			} else if (target < A[mid]) {
				//in the left side
				end = mid;
			} else {
				start = mid;
			}
		}
//    	System.out.println("start = " + start);
//    	System.out.println("end = " + end);
    	if (A[end] == target) {
			return end;
		}
    	if (A[end] < target) {
			return end + 1;
		}
    	if (A[start] == target) {
			return start;
		}
    	return start + 1;
    }