Skip to main content

6. Search Insert Position

easyAsked at Box

Find an index in a sorted array using binary search — Box uses this when inserting a new file version into a sorted version-history list.

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

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. Must run in O(log n) time.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i], target <= 10^4
  • nums has distinct values, sorted ascending

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 the array until value >= 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 binary search; return left at end.

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:

Box-specific tips

Box graders want clean lower-bound binary-search with correct boundary semantics — they map this to inserting versions in sorted-by-timestamp file histories.

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

Practice these live with InterviewChamp.AI →