35. Search Insert Position

Reformulated question¶

Given a sorted array of distinct integers, return the index of target, or the index where it should be inserted to keep the array sorted, in \(O(\log n)\).

• Example: nums=[1,3,5,6], target=2 -> 1
  • 2 is not present
  • inserting at index 1 gives [1,2,3,5,6]

Key trick¶

Use binary search for the first index where nums[i] >= target.

• If target exists, that index is its position.
• If not, that index is exactly the insertion position.
• After the loop, left is the answer.

Trap¶

• Using right = len(nums) but then reading nums[mid] carelessly.
• Returning a temporary index variable instead of the final binary-search boundary.
• Updating bounds incorrectly:
  • for target < nums[mid], use right = mid - 1 in closed interval search
  • or right = mid in half-open interval search
• Forgetting edge cases:
  • insert at start
  • insert at end
  • single-element array

Why is this question interesting?¶

It is a small binary-search problem where correctness depends on choosing and keeping one invariant.

• It tests whether you really understand boundaries.
• It is also the "lower bound" pattern, reused in many harder problems.

Solve the problem with idiomatic Python¶

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        # Closed interval binary search on [left, right].
        left, right = 0, len(nums) - 1

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

            if nums[mid] < target:
                left = mid + 1
            else:
                # Keep mid as a candidate answer.
                right = mid - 1

        # left is the first index with nums[i] >= target,
        # or len(nums) if target is larger than all elements.
        return left

from bisect import bisect_left

class SolutionBisect:
    def searchInsert(self, nums: list[int], target: int) -> int:
        return bisect_left(nums, target)

Pytest test¶

import pytest

@pytest.mark.parametrize(
    "nums, target, expected",
    [
        ([1, 3, 5, 6], 5, 2),
        ([1, 3, 5, 6], 2, 1),
        ([1, 3, 5, 6], 7, 4),
        ([1, 3, 5, 6], 0, 0),
        ([1], 1, 0),
        ([1], 0, 0),
        ([1], 2, 1),
        ([1, 3], 2, 1),
        ([1, 3, 5], 4, 2),
        ([1, 3, 5], 6, 3),
    ],
)
def test_search_insert(nums, target, expected):
    assert Solution().searchInsert(nums, target) == expected

Comment my solution¶

Your code is close, but the interval logic is inconsistent.

• You start with a half-open range:
  • left, right = 0, len(nums)
• But your updates do not match that pattern:
  • right = mid + 1 should not happen when going left
  • that can keep the range wrong or stuck
• index is not reliable:
  • it may be uninitialized if the loop never runs
  • it is better to return left
• For this problem, the simplest correct invariant is:
  • keep searching while left <= right
  • move left right when nums[mid] < target
  • otherwise move right left
  • return left

# WRONG
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (right + left) // 2
            if target == nums[mid]:
                return mid
            if target < nums[mid]:
                index = mid - 1
                right = mid + 1
            else:
                index = mid + 1
                left = mid + 1
        return index