Skip to main content

6. Search Insert Position

easyAsked at Coupang

Binary-search for an insert index — Coupang uses this to test binary-search instincts that show up later in price-range filter problems.

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. You must write an algorithm with O(log n) runtime.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains 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 until you pass 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

Classic lo/hi loop, return lo on miss.

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:

Coupang-specific tips

Coupang interviewers will probe whether you used the half-open interval pattern; that pattern is the house standard for their price-tier lookup.

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

Practice these live with InterviewChamp.AI →