```
public class Solution {
private int binSearch(int[] a, int key, int low, int high) {
if( low < high ) {
int mid = (low+high) / 2;
if( key == a[mid] ) return mid;
else if( key > a[mid] ) return binSearch(a, key, mid+1, high);
else return binSearch(a, key, low, mid-1);
}
else {
if( low == high ) return key <= a[high] ? high: high+1;
else return low;
}
}
public int searchInsert(int[] nums, int target) {
return binSearch(nums, target, 0, nums.length-1);
}
}
```