35. Search Insert Position

Problem¶

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 it 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.

Python solution¶

import bisect

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

        while l <= r:
            mid = (l + r) // 2

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

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

    def searchInsert_2(self, nums: list[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

Comment on 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

# WRONG (tried later - 2026-07-28)
# I starts to have more clarity about binary search
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2

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

        return left

Solution().searchInsert([1], 2) # returns 0 but it should be 1
Solution().searchInsert([1, 3, 5, 6], 7) # returns 3 but it should be 4