35. Search Insert Position

Quick Identifier

• Topic: binary-search
• Pattern: Binary Search (Lower bound)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, LinkedIn, Bloomberg
• Frequency: High
• LeetCode: 35

Quick Sights

• Time Complexity: O(log n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given sorted distinct integers nums and target, return the index where target should be inserted to keep order: the smallest index index such that nums[index] >= target.

Concept Explanation

Given sorted distinct integers nums and target, return the index where target should be inserted to keep order: the smallest index index such that nums[index] >= target.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• “Search insert position” or first position not less than target
• Sorted array; answer is an index in [0, len(nums)]
• Classic “lower bound” phrasing

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) time / O(1) space — scan until nums[index] >= target or end.
• Better — binary search on answer index — same as optimal.
• Optimal — O(log n) time / O(1) space — half-open window [left, right) with right = len(nums); narrow until left == right.

Optimal Solution

Go

func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

JavaScript

function searchInsert(nums, target) {
	let left = 0;
	let right = nums.length;
	while (left < right) {
		const mid = left + Math.floor((right - left) / 2);
		if (nums[mid] < target) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return left;
}

Walkthrough

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

Invariant: the insert position is always in [left, right); when left == right, that index is the lower bound.

Edge Cases

• Target smaller than nums[0] → 0.
• Target larger than all → len(nums).
• Empty array → 0.
• Single element: less / equal / greater than that element.

Pitfalls

• Using inclusive right = len(nums)-1 with wrong loop condition and never returning len.
• Confusing “insert after duplicates” with lower bound; this problem wants first ≥ target for distinct inputs.

Similar Problems

• 704. Binary Search — exact match variant with closed interval.
• 74. Search a 2D Matrix — virtual sorted axis via row-major rank.
• 33. Search in Rotated Sorted Array — partition-aware comparisons inside binary search.

Variants

• Count smaller after sorting — merge sort / BIT; different objective than insert index.
• Strict upper bound (first > target) — adjust nums[mid] <= target branch.

Mind-Map Tags

#binary-search #lower-bound #sorted-array #half-open-interval