Log inSign up
easyLeetCodeNot Started

Search Insert Position

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on LeetCode
Lesson

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 would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1 · Target Found in Middle:

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is found at index 2.

Example 2 · Target Inserted in Middle:

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 would be inserted between 1 and 3, which is index 1.

Example 3 · Target Larger than All Elements:

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 is greater than 6, so it would be appended at index 4.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mathematical proof of why low converges to the insertion index.
  • Implement the Lower Bound pattern (nums[mid] >= target).
  • Differentiate exact match search from boundary insertion search.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted array search with fallback insertion point
  • Find first position satisfying nums[i] >= target
  • Requirement for O(log N) runtime

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = n.
  • If nums[mid] >= target, record ans = mid and search left (high = mid - 1).
  • If nums[mid] < target, search right (low = mid + 1).
  • Return ans (or low directly when loop ends).

Connected Patterns:

Lower BoundUpper BoundBinary SearchFirst and Last Position of Element

1. Linear Scan Insertion Point

Intuition

Scan the array from left to right. The first element nums[i] that is greater than or equal to target marks the insertion index. If no such element exists, target is larger than all elements; return nums.length.

When to apply: Unsorted or small arrays where O(N) is acceptable.

Algorithm

  1. Step 1: Iterate index i from 0 to nums.length - 1.
  2. Step 2: If nums[i] >= target, return index i immediately.
  3. Step 3: If loop completes without returning, return nums.length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int searchInsert(vector<int>& nums, int target) {
9 for (int i = 0; i < (int)nums.size(); i++) {
10 if (nums[i] >= target) return i;
11 }
12 return nums.size();
13 }
14};
15
16int main() {
17 Solution sol;
18 vector<int> nums = {1, 3, 5, 6};
19 cout << "Linear search insert index: " << sol.searchInsert(nums, 2) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N) — Worst case scans all N elements when target exceeds every element.
  • Space complexity: O(1) — Uses a single index counter variable.

2. Explicit Answer Variable Binary Search

Intuition

Define ans = nums.length. In binary search, whenever nums[mid] >= target, we have found a candidate insertion index; record ans = mid and move left (high = mid - 1) to find a smaller valid index.

When to apply: Clear conceptual framework for lower bound search.

Algorithm

  1. Step 1: Initialize low = 0, high = nums.length - 1, and ans = nums.length.
  2. Step 2: Loop while low <= high.
  3. Step 3: Calculate mid = low + (high - low) / 2.
  4. Step 4: If nums[mid] >= target, record ans = mid and search left (high = mid - 1).
  5. Step 5: If nums[mid] < target, search right (low = mid + 1).
  6. Step 6: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int searchInsert(vector<int>& nums, int target) {
9 int low = 0, high = (int)nums.size() - 1;
10 int ans = nums.size();
11
12 while (low <= high) {
13 int mid = low + (high - low) / 2;
14 if (nums[mid] >= target) {
15 ans = mid;
16 high = mid - 1;
17 } else {
18 low = mid + 1;
19 }
20 }
21 return ans;
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {1, 3, 5, 6};
28 cout << "Explicit ans BS result: " << sol.searchInsert(nums, 2) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval each step in log2(N) iterations.
  • Space complexity: O(1) — Uses constant auxiliary variables.

3. Direct Pointer Convergence Binary Search (Gold Standard)

Intuition

Run standard binary search: if nums[mid] == target, return mid. If nums[mid] < target, low = mid + 1. If nums[mid] > target, high = mid - 1. When low > high, low is guaranteed to be at the exact insertion position.

When to apply: Industry standard optimal solution for insertion index and lower bound problems.

Algorithm

  1. Step 1: Initialize low = 0 and high = nums.length - 1.
  2. Step 2: While low <= high, calculate mid = low + (high - low) / 2.
  3. Step 3: If nums[mid] == target, return mid immediately.
  4. Step 4: If nums[mid] < target, advance low = mid + 1.
  5. Step 5: If nums[mid] > target, retreat high = mid - 1.
  6. Step 6: When loop terminates (low > high), return low as the insertion index.

Search Insert Position Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initialize low = 0, high = 3
Visual state
Values and pointers at this exact step
array
S
1
3
5
6
0
↑ low
1
↑ mid
2
3
↑ high
Variables at this step
low
0
high
3
mid
1
midVal
3
target
2
Check / comparison
nums[mid] = 3 vs target = 2 -> 3 > 2
Decision / next transition
Since 3 > 2, target must be in left half. Update high = mid - 1 = 0.
Why this step matters

Initialize low = 0, high = 3. Calculate mid = 0 + (3 - 0) / 2 = 1. Value at mid is nums[1] = 3.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int searchInsert(vector<int>& nums, int target) {
9 int low = 0, high = (int)nums.size() - 1;
10
11 while (low <= high) {
12 int mid = low + (high - low) / 2;
13
14 if (nums[mid] == target) {
15 return mid;
16 } else if (nums[mid] < target) {
17 low = mid + 1;
18 } else {
19 high = mid - 1;
20 }
21 }
22 return low; // Pointer convergence property
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> nums = {1, 3, 5, 6};
29 int target = 2;
30 cout << "Search Insert Position for " << target << ": " << sol.searchInsert(nums, target) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(log N) — Logarithmic binary search dividing search window by 2 in each iteration.
  • Space complexity: O(1) — Uses only two pointer variables low and high.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Scan array left to right until finding nums[i] >= target.Sequential search
2.Explicit ans Binary SearchO(log N)O(1)Store candidate index in ans whenever nums[mid] >= target.None
3.Direct Pointer Convergence Binary SearchOptimalO(log N)O(1)Standard binary search returning low directly upon loop termination.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning -1 instead of low when target is absent.

Pitfall 2:

Using high = mid instead of high = mid - 1 (can cause infinite loop).

Crucial Edge Cases to Validate:

  • Target Smaller than First Element: nums = [2, 4, 6], target = 1 -> returns index 0.
  • Target Larger than Last Element: nums = [2, 4, 6], target = 8 -> returns index 3 (nums.length).
  • Target Matches Exact Element: nums = [1, 3, 5], target = 3 -> returns index 1 immediately.
  • Single Element Array [5], target = 2 -> returns 0; target = 7 -> returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight that this problem is mathematically identical to C++ std::lower_bound.
  2. Walk through pointer convergence (why low is at the correct insertion index) to impress the interviewer.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When binary search terminates with target absent from the array, what does the low pointer represent?

2.If target is greater than all elements in nums (e.g. nums = [1, 3, 5], target = 10), what index is returned?

Back to DSA Sheet