Skip to main content

6. Search Insert Position

easyAsked at Vercel

Given a sorted array and a target, return the index where the target is or where it should be inserted. Vercel asks this to confirm you can write a clean binary search with the 'lower-bound' semantic — exactly what their route-matching trie uses to find the matching prefix.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel routing-team screen; lower-bound bug expected to be caught.
  • Blind (2026-Q1)— Listed in Vercel platform engineer onsite recap.

Problem

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.

Constraints

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

Examples

Example 1

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

Example 2

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

Example 3

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

Approaches

1. Linear scan

Walk left to right; return first index where nums[i] >= target, else nums.length.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
}

Tradeoff: Violates the O(log n) constraint. Mention only to contrast.

2. Binary search lower bound (optimal)

Maintain [lo, hi] = [0, n]. While lo < hi, take mid and narrow: if nums[mid] < target, lo = mid + 1; else hi = mid. Return lo.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff: Classic lower-bound binary search. The trick: hi starts at n (not n-1) so the answer 'past the end' (target larger than all) falls out naturally as lo === n.

Vercel-specific tips

Vercel grades for the lower-bound variant specifically: hi = n, half-open interval, return lo. They'll ask you to walk through 'what if the target is smaller than every element' and 'what if larger than all' — both must work without a special case. Bonus signal: explaining `(lo + hi) >>> 1` vs `(lo + hi) / 2 | 0` for overflow safety in larger languages.

Common mistakes

  • Using lo <= hi with hi = n - 1 — works for found case but mishandles 'insert past the end'.
  • Computing mid as `(lo + hi) / 2` and forgetting Math.floor — works in JS for small inputs but loses the habit.
  • Returning -1 when not found — that's LC 704; this problem returns the insert position.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Find first AND last position of target (LC 34).
  • What if duplicates are allowed? Return the first occurrence's index.
  • Implement upper-bound — first index where nums[i] > target.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why hi = n instead of n - 1?

Because the answer can legitimately BE n — when target is greater than every element. Starting hi at n makes that a valid output rather than a special case.

Half-open vs inclusive interval — which is the Vercel preference?

Half-open [lo, hi) is more robust because the loop invariant 'answer is in [lo, hi)' is preserved trivially. Inclusive [lo, hi] works but tempts off-by-one bugs.

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →