35 Search Insert Position

1. Description

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.

You must write an algorithm with O(log n) runtime complexity.

Constraints:

1. \(1 \leq nums.length \leq 10^{4}\)
2. \(-10^{4} \leq nums[i] \leq 10^{4}\)
3. nums contains distinct values sorted in ascending order
4. \(-10^{4} \leq target \leq 10^{4}\)

1.1. Examples:

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

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

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

2. Solution

2.1. Understanding the problem

How do we know that this is a Binary Search problem? Two points:

1. it requires O(log n) time complexity, but this is not the deciding factor.
2. The task asks us to find a certain index/position by comparing a target element with an ordered list of elements.
   1. It could be asking inexplicitly but you need to be able to figure out what is really being asked.

2.2. Algorithm

Binary Search.

2.3. Code

Listing 1: 35 Search Insert Position my solution

def searchInsert(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    left_idx = 0
    right_idx = len(nums) - 1

    while left_idx <= right_idx:
        mid = left_idx + (right_idx - left_idx) // 2
        curr = nums[mid]

        if curr == target:
            return mid
        elif curr > target:
            right_idx = mid - 1
        else:
            left_idx = mid + 1

    # [1, target, curr]
    # right_idx, left_idx, left_idx+1
    # [curr, target, 4]
    # right_idx, left_idx, left_idx+1
    return left_idx


# tests
nums, target, result = [0], 0, 0
print(searchInsert(nums, target) == result)

nums, target, result = [0], 1, 1
print(searchInsert(nums, target) == result)

nums, target, result = [0], -1, 0
print(searchInsert(nums, target) == result)

nums, target, result = [0, 2], 1, 1
print(searchInsert(nums, target) == result)


nums, target, result = [0, 2, 3], 0, 0
print(searchInsert(nums, target) == result)


nums, target, result = [0, 2, 3], 4, 3
print(searchInsert(nums, target) == result)

Listing 2: 35 Search Insert Position my solution-results

True
True
True
True
True
True

2.3.1. Complexity

2.3.1.1. Time complexity:

O(log n)

2.3.1.2. Space complexity:

O(1)

2.4. Leetcode solution

nil but basically the same implementation.

Listing 3: 35 Search Insert Position leetcode solution

<<imports for typing>>

Listing 4: 35 Search Insert Position leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

Again we know we need to use Binary Search, but the implementation details suck.

Basically we need to under stand what it means to insert an element to the list at position idx. A trivial case is that we can find target in the list, then we return mid.

We now consider when we can't find target in the list and what should we return in the end. First of all, we can easily tell that in this case, the terminating condition for the binary search would be left_idx == right_idx + 1.

By actually inserting target into the list, we then will have something like below:

Table 1: curr < target

curr	target	n
right_idx	left_idx	left_idx + 1

Table 2: curr > target

n	target	curr
right_idx	left_idx	left_idx + 1

We can see from the insertion tables that target is always inserted at the left_idx location.

3.2. Related problems

1. 278 First Bad Version
2. 704 Binary Search
3. [BROKEN LINK: 6705fa69-9835-4076-b293-cd962e3c5828]

4. Log time