35. Search Insert Position

Given a sorted array of distinct integers 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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

Source

Code

In [1]:

def search_insert(nums, target):
    """iterative approach."""
    # uncoment to make faster
    # if target <= nums[0]:
    #     return 0
    # if nums[-1] == target:
    #     return len(nums)-1
    # if nums[-1] < target:
    #     return len(nums)
    left = 0
    right = len(nums)-1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return left

In [2]:

def search_insert(nums, target):
    """variation of above solution"""
    left = 0
    right = len(nums)
    mid = (left + right) // 2
    while left < right:
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid+1
        else:
            right = mid
        mid = (left + right) // 2
    return mid

In [3]:

from bisect import bisect_left

def search_insert(nums, target):
    """Cheating method using bisert."""
    return bisect_left(nums, target)

Check

In [4]:

nums = [1, 3, 5, 6]
target = 5
search_insert(nums, target)

Out[4]:

In [5]:

nums = [1, 3, 5, 6]
target = 2
search_insert(nums, target)

Out[5]:

In [6]:

nums = [1, 3, 5, 6]
target = 7
search_insert(nums, target)

Out[6]:

In [7]:

nums = [1, 3, 5, 6]
target = 0
search_insert(nums, target)

Out[7]:

In [8]:

nums = [1]
target = 0
search_insert(nums, target)

Out[8]:

In [9]:

nums = []
target = 10
search_insert(nums, target)

Out[9]:

Follow up:

Can you solve it both iteratively and recursively?

Code

In [1]:

def search_insert(nums, target):
    """recursive solution"""
    def bs_recur(left, right, target):
        nonlocal nums

        # base cases
        if left > right:
            return left
        mid = (left + right) // 2
        if target == nums[mid]:
            return mid

        # recursive relation
        if target < nums[mid]:
            return bs_recur(left, mid - 1, target)
        return bs_recur(mid + 1, right, target)

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