Search Insertion Position - Recursion

search-insert.cs

public int SearchInsert(int[] nums, int target) {
    return Search(nums, target, 0, nums.Length - 1);
}

private int Search(int[] nums, int target, int startingIndex, int endingIndex) {
    int middleIndex = startingIndex + (endingIndex + 1 - startingIndex) / 2;
    
    if (startingIndex == endingIndex) {
        if (target <= nums[startingIndex]) {
            return startingIndex;
        } else {
            return startingIndex + 1;
        }
    } 
    else if (endingIndex - startingIndex == 1) {
        if (target <= nums[startingIndex]) {
            return startingIndex;
        } else if (target <= nums[endingIndex]) {
            return endingIndex;
        } else {
            return endingIndex + 1;
        }
    }
    else if (target == nums[middleIndex])
    {
        return middleIndex;
    }
    else if (target < nums[middleIndex]) {
        return Search(nums, target, startingIndex, middleIndex); 
    } else {
        return Search(nums, target, middleIndex, endingIndex);
    }
}