LeetCode · #35

Search Insert Position Solution

Given a sorted array and a target, return the index if found — or the index where it would be inserted.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #35

🏗️

Pattern

Binary Search — lower bound

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 would be inserted to keep the array sorted. You must write an O(log n) algorithm.

Example 1

 Input: nums = [1,3,5,6], target = 5 Output: 2 

Example 2

 Input: nums = [1,3,5,6], target = 2 Output: 1 // 2 would be inserted at index 1 (between 1 and 3) 

Constraints

 • 1 ≤ nums.length ≤ 10⁴ • -10⁴ ≤ nums[i] ≤ 10⁴ • nums contains distinct values sorted in ascending order • -10⁴ ≤ target ≤ 10⁴ 

Section Two · Approach 1

Linear Scan — O(n)

Walk through the array. Return the first index where nums[i] >= target. If no such index, insert at the end.

Problem: O(n) ignores sorted property. This is exactly the "lower bound" binary search — find the first position where nums[i] >= target.

Java — Linear Scan

 class Solution {
public int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
if (nums[i] >= target) return i;
return nums.length;
    }
}

Python — Linear Scan

 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)

Metric	Value
Time	O(n)
Space	O(1)

Section Three · Approach 2

Binary Search (Lower Bound) — O(log n)

This is the classic lower bound binary search. Find the leftmost position where the target could be inserted. When nums[mid] < target, move right. Otherwise, the answer is at mid or earlier — move left boundary.

💡 Mental model: You're looking for a seat in a sorted row. If the seat number at mid is too small, you go right. If it's equal or larger, this could be your seat — but there might be an earlier one, so you keep searching left. When the search ends, left is exactly where you sit (or insert).

Algorithm

Step 1: left = 0, right = n (note: not n-1, because insert position could be past the end).
Step 2: While left < right: compute mid.
Step 3: If nums[mid] < target → left = mid + 1.
Step 4: Else → right = mid.
Step 5: Return left.

🎯 Lower bound vs exact search:

Standard binary search returns -1 if not found. Lower bound always returns a valid insert position.
The difference: use left < right (not ≤) and right = mid (not mid-1).
This converges L and R to the insertion point.
This is equivalent to C++ std::lower_bound or Python's bisect.bisect_left.

Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 3, 5, 6], target = 2:

Lower Bound Binary Search — find insertion point

Section Five · Implementation

Code — Java & Python

Java — Lower Bound Binary Search

 class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
                left = mid + 1;
else
right = mid;
        }
return left;
    }
}

Python — Lower Bound (or bisect_left)

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear Scan	O(n)	O(1)	Simple but ignores sorted
Lower Bound BS ← optimal	O(log n)	O(1)	Classic lower-bound search

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Insert at start	`[2,4,6], target=1`	All elements ≥ target → left stays 0 → insert at 0.
Insert at end	`[2,4,6], target=7`	All elements < target → left reaches n → insert at end.
Exact match	`[2,4,6], target=4`	Found → return index 1. Lower bound naturally finds it.
Single element	`[3], target=3`	mid=0, nums[0]=3 ≥ 3 → R=0 → L==R==0.

⚠ Common Mistake: Initializing right = n - 1 instead of right = n. The insert position can be at index n (past the end), so the search range must include it. With right = n - 1, inserting after the last element is missed.

← Back to Binary Search problems

LearningTree

LC 35 · Search Insert Position — Solution & Explanation | DSA Guide