Search Insert Position

1. Define the 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 if it were inserted in order, keeping the array sorted. You must write an algorithm with O(log n) runtime complexity. This is a boundary search for the first index whose value is not smaller than target — low lands there whether or not target is present.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums_i ≤ 10⁴
nums contains distinct values sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

Example

Inputnums = [1, 3, 5, 6], target = 5

Output2

Explanation 5 is present in nums at index 2.

2. Know the words first

In plain terms

Boundary search: A binary search that looks for the first index where a condition flips from false to true, instead of an exact value match.

3. Visualize the solution

Narrow to the first index that is not smaller than target

Statusinit

low=0, high=3, mid=1 (value 3). target 5 > 3, so low moves to 2.

What happens in this step

low=0, high=3
mid = 0 + floor((3-0)/2) = 1, nums[1] = 3

3 < 5, so the insertion point is after mid — low becomes 2.

Step 1 of 3

Steps to visualize

The row is the whole array; the box marks the part still being searched.
Start low at 0 and high at nums.length - 1.
While low ≤ high, compare nums_mid to target.
If nums_mid < target, the insertion point is after mid, so low = mid + 1.
Otherwise the insertion point is at or before mid, so high = mid - 1.
When the loop ends, low is exactly the answer — the target or its insertion point.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Narrow to the first index that is not smaller than target

Statusinit

low=0, high=3, mid=1 (value 3). target 5 > 3, so low moves to 2.

What happens in this step

low=0, high=3
mid = 0 + floor((3-0)/2) = 1, nums[1] = 3

3 < 5, so the insertion point is after mid — low becomes 2.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function searchInsert(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return low;
}

Time: O(log n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 3, 5, 6], target = 5`	`2`	example from the docstring, target present
`nums = [1, 3, 5, 6], target = 2`	`1`	target absent, inserted between two existing values
`nums = [1, 3, 5, 6], target = 7`	`4`	target larger than every element, inserted at the end
`nums = [1, 3, 5, 6], target = 0`	`0`	target smaller than every element, inserted at the start
`nums = [1], target = 1`	`0`	smallest valid input, target present
`nums = [5], target = 2`	`0`	smallest valid input, target absent and smaller
`nums = [1, 3, 5, 6], target = 1`	`0`	target present at the first index

Search Insert Position