Search Insert Position: Lower bound Pattern

Learning Outcome

After this lesson, you should be able to modify binary search to return an insertion boundary instead of only found/not-found.

Problem Statement

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 should be inserted in order.

Brute Force Approach

Scan from left to right and return the first index where nums[i] >= target. If none exists, return n.

This is clear, but it costs O(n) and ignores sorted search.

Optimized Approach

Use lower-bound binary search. Keep the invariant that the answer is the first position where the value is greater than or equal to the target. Search in the half-open range [left, right).

When nums[mid] < target, the answer is after mid. Otherwise, mid could be the answer, so keep it by moving right = mid.

Exact Pseudocode

left = 0
right = length(nums)
while left < right:
  mid = left + (right - left) // 2
  if nums[mid] < target:
    left = mid + 1
  else:
    right = mid
return left
  

Reference Code

class Solution:
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)

        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left
  

Sample Dry Run

Complexity

Edge Cases

• Target smaller than all elements returns 0.
• Target larger than all elements returns n.
• Target exactly equals an existing value.

Interview Checklist

• Use half-open range [left, right) for clean insertion logic.
• Return left after the loop.
• Know this is the lower-bound pattern.

FAQs

The valid insertion position can be after the last element.

The first index whose value is greater than or equal to the target.

Binary search for a boundary, not just for equality.