DSA Tracker

Visualize

Search Insert Position

time O(log n)space O(1)

The insight: binary search doesn't just locate an exact match — the way it narrows left and right also pins down exactly where the value would go if it were missing. Every time nums[mid] is too small, left moves past it, so everything before the new left is provably smaller than the target; every time nums[mid] is too big, right moves before it, so everything after the new right is provably bigger. When the loop ends, left sits exactly on the boundary between "too small" and "too big" — that boundary IS the insertion point, whether or not the target was actually present. This trace shows the case where target=5 IS found at index 2, short-circuiting the loop before it ever needs to fall back on that boundary.

Details

Animated on: 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 inserted in order.

Problem:Search Insert PositionEasy

Pattern:Binary Search on Sorted Data

Binary Search

step 1 / 6

1
[0]
3
[1]
5
[2]
6
[3]

Initialize left=0 and right=3 (last index of nums).

  • left=0· arr[0] = 1
  • right=3· arr[3] = 6
Pseudocode
1FUNCTION searchInsert(nums, target):
2  left = 0, right = the length of nums - 1
3  WHILE left <= right:
4    mid = (left + right) / 2, rounded down
5    IF nums[mid] === target:  RETURN mid
6    IF nums[mid] < target:  left = mid + 1
7    ELSE:  right = mid - 1
8  END WHILE
9  RETURN left
10END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 6 steps
  1. Initialize left=0 and right=3 (last index of nums).
  2. Compute mid = floor((0+3)/2) = 1.
  3. nums[1] = 3 < target 5. Since 3 < 5, move left past mid: left = mid + 1 = 2.
  4. Compute mid = floor((2+3)/2) = 2.
  5. nums[2] = 5 === target. Found at index 2!
  6. Return mid=2 directly — the target 5 is found at index 2. (If it weren't present, the loop would instead exit and 'return left' — the natural insertion point.)

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Search Insert Position in the editorAll Binary Search problemsBack to roadmap