```
public int searchInsert(int[] nums, int target) {
return searchInsertUtil(nums, 0, nums.length-1, target);
}
private int searchInsertUtil(int[] nums, int low, int high, int target) {
if (low > high) return low;
int mid = (low + high) / 2;
if (target < nums[mid]) {
// Recurse on the left half
return searchInsertUtil(nums, low, mid - 1, target);
} else if (target > nums[mid]) {
// Recurse on the right half
return searchInsertUtil(nums, mid + 1, high, target);
}
return mid;
}
```