Skip to main content

6. Search Insert Position

easyAsked at Glassdoor

Find the index where a target should be inserted in a sorted array — Glassdoor uses this to grade binary-search precision under boundary conditions.

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 inserted in order. You must write an O(log n) algorithm.

Constraints

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

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 an 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: shrink [lo, hi) until lo lands 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 mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff:

Glassdoor-specific tips

Glassdoor grades whether you nail the half-open interval — bonus signal is mentioning the integer-overflow safe midpoint, since their salary-binning service has been bitten by it before.

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

Practice these live with InterviewChamp.AI →