LeetCode 35: Search Insert Position

Problem Restatement

We are given a sorted array of distinct integers nums and an integer target.

If target exists in nums, return its index.

If target does not exist, return the index where it should be inserted so that the array remains sorted.

The required runtime is O(log n), so the intended solution is binary search. The constraints say nums is sorted in ascending order and contains distinct values.

Input and Output

Function shape:

def searchInsert(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

nums = [1, 3, 5, 6]
target = 5

The value 5 appears at index 2.

Return:

2

Example 2:

nums = [1, 3, 5, 6]
target = 2

The value 2 does not appear.

To keep the array sorted, it should be inserted between 1 and 3.

Return:

1

Example 3:

nums = [1, 3, 5, 6]
target = 7

The value 7 is greater than every number in the array.

It should be inserted at the end.

Return:

4

First Thought: Linear Search

The simplest approach is to scan from left to right.

The first index where nums[i] >= target is the answer.

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num >= target:
                return i

        return len(nums)

This works because the array is sorted.

If we find a number equal to target, its index is the answer.

If we find a number greater than target, then target should be inserted before it.

If no such number exists, target belongs at the end.

Problem With Linear Search

Linear search takes O(n) time.

The problem requires O(log n) time. Since the array is sorted, binary search can find the same boundary faster.

We want the first index where:

nums[i] >= target

This is also called the lower bound of target.

Key Insight

The answer is a boundary.

For every index before the answer:

nums[i] < target

For the answer index and every index after it:

nums[i] >= target

So we can binary search for the first position where nums[i] >= target.

Use a half-open interval:

[left, right)

Start with:

left = 0
right = len(nums)

This lets the answer be len(nums) when target is larger than every element.

Algorithm

Initialize:

left = 0
right = len(nums)

While left < right:

1. Compute mid.
2. If nums[mid] >= target, the answer is at mid or to its left, so set right = mid.
3. Otherwise, nums[mid] < target, so the answer is to the right, and set left = mid + 1.

When the loop ends, left == right.

Return left.

Correctness

The algorithm maintains a search interval [left, right) that always contains the insertion position.

If nums[mid] >= target, then mid is a valid insertion candidate because placing target at or before mid can preserve sorted order. The first valid position may be mid or earlier, so keeping the left half is correct.

If nums[mid] < target, then target cannot be inserted at mid or before mid while preserving sorted order, because nums[mid] must remain before target. Therefore, the insertion position must be after mid.

Each step keeps the side that contains the first index where nums[i] >= target. When the interval becomes empty except for one boundary, left is exactly that index.

If target exists, this boundary is its index. If target does not exist, this boundary is where it should be inserted.

Complexity

Implementation

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums)

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1

        return left

Code Explanation

We search the half-open interval [left, right).

left = 0
right = len(nums)

Using right = len(nums) is useful because the insertion position can be after the last element.

The loop continues while there is still more than one possible boundary.

while left < right:

The midpoint is:

mid = left + (right - left) // 2

If nums[mid] is greater than or equal to target, then mid may be the answer.

if nums[mid] >= target:
    right = mid

Otherwise, nums[mid] is too small, so the answer must be after mid.

else:
    left = mid + 1

At the end, left is the first index where target can be placed.

return left

Testing

def check(nums: list[int], target: int, expected: int) -> None:
    actual = Solution().searchInsert(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([1, 3, 5, 6], 5, 2)
    check([1, 3, 5, 6], 2, 1)
    check([1, 3, 5, 6], 7, 4)
    check([1, 3, 5, 6], 0, 0)
    check([1], 1, 0)
    check([1], 0, 0)
    check([1], 2, 1)
    check([-10, -3, 0, 4, 9], -3, 1)
    check([-10, -3, 0, 4, 9], 5, 4)

    print("all tests passed")

run_tests()

Test meaning: