```
class Solution {
private:
int searchInsertHelper(vector<int>& nums, int target, int left, int right)
{
if(left>right)
return left;
int mid = (left+right)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target)
return searchInsertHelper(nums, target, left, mid-1);
else
return searchInsertHelper(nums, target, mid+1, right);
}
public:
int searchInsert(vector<int>& nums, int target) {
return searchInsertHelper(nums, target, 0, nums.size()-1);
}
};
```