```
public class Solution {
private int helper(int[] nums, int start, int end, int target) {
if(start==end) {
if(nums[start]==target)
return start;
else if(target > nums[start])
return -(start+1)-1; // decrease by additional 1 to differentiate with 0
else
return -start-1; // decrease by additional 1 to differentiate with 0
}
int mid = (start+end)/2;
if(nums[mid] == target)
return mid;
else if(target > nums[mid])
return helper(nums, mid+1, end, target); // note mid must not be the insertion point,so start with mid+1
else
return helper(nums, start, mid, target); // note both start and mid must be inclusive cause mid can be the insertion point
}
public int searchInsert(int[] nums, int target) {
int res = helper(nums, 0, nums.length-1, target);
return res>=0 ? res : -(res+1);
}
}
```