```
public class Solution {
public int SearchInsert(int[] nums, int target) {
return SearchInsert(nums, target, 0, nums.Length-1);
}
public int SearchInsert(int[] nums, int target, int low, int high)
{
if (low == high)
{
return (target > nums[low]) ? low + 1 : low;
}
while(low + 1 < high)
{
int mid = low + (high - low)/2;
if (target < nums[mid] && target < nums[mid-1])
{
high = mid -1;
}
else if (target > nums[mid] && target > nums[mid + 1])
{
low = mid + 1;
}
else
{
// Even though we know we know the number = mid,
// we need to find the first position that this number starts at
high = mid;
}
}
// Now there are just two elements pointed to by low and high
if (target <= nums[low])
{
return low;
}
else if (target > nums[high])
{
return high + 1;
}
else {
// Its in between these two elemets
return low + 1;
}
}
}
```