Search Insert Position — DSA Visualizer

Problem

Given a sorted array of distinct integers nums and a target value, return the index if the target is found. If not, return the index where it would be inserted in order. You must write an algorithm with O(log n) runtime complexity.

Example 1

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

Output: 2

Explanation: 5 is found at index 2.

Example 2

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

Output: 1

Explanation: 2 would be inserted between index 0 (value 1) and index 1 (value 3).

Example 3

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

Output: 4

Explanation: 7 is larger than all elements — insert at the end.

Constraints: 1 ≤ nums.length ≤ 10⁴ | −10⁴ ≤ nums[i], target ≤ 10⁴ | All integers in nums are distinct and sorted ascending.

Array

target —

Variables

—

mid

—

nums[mid]

—

comparison

—

Step Logic

Press ▶ Play or Next Step to begin the animation.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Init lo = 0, hi = nums.length − 1

While lo ≤ hi: compute mid = lo + (hi−lo)/2

If nums[mid] == target → return mid (found)

If nums[mid] < target → lo = mid + 1 (search right half)

Else → hi = mid − 1 (search left half)

Loop ends: lo is the insertion point — return lo

Time

O(log n)

Space

O(1)

Why lo is the Insert Position

Loop invariant: at every step the answer lies in [lo, hi+1]. When lo > hi the range collapses and lo points to the first index where nums[lo] > target — exactly where target must be inserted to preserve sorted order. This works whether target is smaller than all elements (lo stays 0), larger than all (lo becomes n), or anywhere in between.