35. Search Insert Position

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

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax