Search Insert Position DSA Solution - Lower Bound - Study Chapter | QuizMaker

Search Insert Position explained with brute force, lower-bound binary search, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 9m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 3: Binary Search

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.

Input	Output	Why
`nums = [1,3,5,6]`, `target = 5`	`2`	5 exists at index 2.
`target = 2`	`1`	2 should be inserted before 3.

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

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

Sample Dry Run

left	right	mid	nums[mid]	Action
0	4	2	5	5 >= 2, move right to 2
0	2	1	3	3 >= 2, move right to 1
0	1	0	1	1 < 2, move left to 1
1	1	-	-	Return 1

Complexity

Measure	Value	Reason
Time	O(log n)	The range is halved each step.
Space	O(1)	Only boundaries are stored.

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

Why is right initialized to n?

The valid insertion position can be after the last element.

What does lower bound mean?

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

What is the core pattern?

Binary search for a boundary, not just for equality.