Skip to main content

6. Search Insert Position

easyAsked at Roblox

Find the index where a target would be inserted in a sorted array.

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

Problem

Given a sorted array of distinct integers and a target value, return its index if found. If not, return the index where it would be inserted to keep the array sorted. The algorithm must run in O(log n) time.

Constraints

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

Walk until first element >= 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 search returning the insertion index when not found.

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:

Roblox-specific tips

Roblox uses binary search to probe whether you can hold loop invariants under stress — a key skill when implementing matchmaking tier insertion.

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 Roblox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →