35. Search Insert Position

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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