Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Modify binary search’s return basecase

Code

    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def mod_bin_search(nums, start, end, target):
            if start > end:
                return start
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] > target:
                return mod_bin_search(nums, start, mid - 1, target)
            else:
                return mod_bin_search(nums, mid + 1, end, target)

        return mod_bin_search(nums, 0, len(nums) - 1, target)

The only change from binary search is to return the start if start > end. Need to consider three situations:

1. target smaller than all
   If smaller than all, then the start will never move and end will eventually be -1. So we return start
2. target larger than all
   in the last round, we have a singleton search range and will will call mod_bin_search(nums, mid + 1, end, target). This intern will give us start = end + 1. And that is the position we want.
3. target stuck between
   In the third to last function call, we will have a search range of 2. mid will be the first number. Since num[mid] < target, it will call mod_bin_search(nums, mid + 1, end, target). It will give us a singleton search range and that number will be larger than target. It is case 1. So we return start as well.

In all three cases, we return start