Skip to main content

6. Search Insert Position

easyAsked at MercadoLibre

Find the index where a target should 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 the index where the target is found. If not found, return the index where it would be inserted in order. You must write an algorithm with O(log n) runtime.

Constraints

  • 1 <= nums.length <= 10^4
  • nums is sorted ascending with distinct 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. Brute force

Linear scan for the first index >= 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 lower bound

Shrink [lo, hi] until lo points at insertion index.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const m = (lo + hi) >> 1;
    if (nums[m] < target) lo = m + 1;
    else hi = m;
  }
  return lo;
}

Tradeoff:

MercadoLibre-specific tips

MercadoLibre cares about clean half-open bounds here — bid insertion in their auction sub-systems needs the same exact-O(log n) guarantee.

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

Practice these live with InterviewChamp.AI →