Skip to main content

6. Search Insert Position

easyAsked at Dropbox

Return the index where a target belongs in a sorted array; Dropbox uses it to probe binary-search hygiene for sorted chunk-offset lookups.

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

Problem

Given a sorted array of distinct integers and a target, return the index if the target is found; otherwise return the index where it would be inserted in order. Algorithm must run in O(log n).

Constraints

  • 1 <= nums.length <= 10^4
  • Array is sorted ascending with distinct values
  • Must be O(log n)

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 you find or pass the 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

Maintain [lo, hi] with hi=length so the final lo is the insertion point. Avoids off-by-one with half-open intervals.

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:

Dropbox-specific tips

Dropbox interviewers will ask you to defend `lo<hi` vs `lo<=hi` — pick one and explain how it ties to the invariant, they grade on that articulation.

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

Practice these live with InterviewChamp.AI →