Skip to main content

6. Search Insert Position

easyAsked at Tesla

Find a target's index in a sorted array, or where it would be inserted.

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

Problem

Given a sorted array nums and a target, return the index where target is found, or the index where it should be inserted. Must run in O(log n).

Constraints

  • 1 <= nums.length <= 10^4
  • nums is sorted ascending
  • -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

Approaches

1. Linear scan

Stop at first index >= target.

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

Tradeoff:

2. Binary search

Standard lower_bound. lo ends at the insertion point.

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

Tradeoff:

Tesla-specific tips

Tesla path-planners rely on bisect over sorted waypoint timestamps — interviewers want to see you write the half-open invariant cleanly without off-by-one mistakes.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →