AlgoMaster Logo

Search Insert Position

Last Updated: March 29, 2026

easy
3 min read

Understanding the Problem

We have a sorted array of unique integers and a target value. If the target already exists in the array, return its index. If it doesn't, return the index where it would need to go to keep the array sorted.

This is really asking one question: what is the leftmost position where target could be placed without breaking the sorted order? If target matches an element, that element's index is the answer. If it doesn't, the answer is the index of the first element greater than target, or the array length if target is larger than everything.

The key observation is that this is exactly the "lower bound" problem from binary search. We're looking for the first index i where nums[i] >= target. That single framing handles both the "found" and "not found" cases in one shot.

Key Constraints:

  • 1 <= nums.length <= 10^4 → The array has at most 10,000 elements. An O(n) scan would be fast enough in practice, but the problem explicitly requires O(log n).
  • nums contains distinct values sorted in ascending order → Sorted + distinct is a strong signal for binary search. No duplicates means there's exactly one correct insert position.
  • -10^4 <= target <= 10^4 → The target could be smaller than all elements (insert at index 0) or larger than all elements (insert at end). Both edge cases matter.

Approach 1: Linear Scan

Intuition

The most straightforward approach: walk through the array from left to right and find the first element that is greater than or equal to the target. If we find such an element, its index is the insert position. If we reach the end without finding one, the target belongs at the end.

This is simple and correct, but it doesn't meet the O(log n) requirement. Still, it's worth understanding because it makes the binary search optimization feel natural. The linear scan checks every element one by one. Binary search does the same logical task but skips half the remaining elements at each step.

Algorithm

  1. Iterate through the array with index i from 0 to n - 1.
  2. If nums[i] >= target, return i. This is either the target itself or the first element larger than it.
  3. If the loop finishes without returning, return n. The target is larger than every element.

Example Walkthrough

1Start scan: i=0, looking for first element >= 2
0
1
i
1
3
2
5
3
6
1/4

Code

The linear scan works but doesn't meet the O(log n) requirement. Since the array is sorted, we can use binary search to eliminate half the search range at each step.

Approach 2: Binary Search

Intuition

The array is sorted. That's the biggest clue. When you have a sorted array and need to find something in O(log n), binary search is the tool.

But here's the subtle part: we're not just searching for a target. We need to find the correct insert position, which means finding the first index where nums[i] >= target. This is called the "lower bound" in binary search terminology, and it handles both cases cleanly:

  • If the target exists, the lower bound is the target's index.
  • If the target doesn't exist, the lower bound is where it would be inserted.

The standard binary search template for lower bound works like this: maintain a search window [left, right). At each step, check the middle element. If it's less than the target, the answer must be in the right half, so move left to mid + 1. If it's greater than or equal to the target, the answer could be mid itself or something to the left, so move right to mid. When the window collapses (left == right), left is the answer.

Algorithm

  1. Set left = 0 and right = nums.length.
  2. While left < right:
    • Compute mid = left + (right - left) / 2 to avoid integer overflow.
    • If nums[mid] < target, set left = mid + 1.
    • Otherwise, set right = mid.
  3. Return left.

Example Walkthrough

1Initialize: left=0, right=4, search range = entire array
0
1
left
1
3
2
5
3
6
search range
1/7

Code