Skip to main content

6. Search Insert Position

easyAsked at Asana

Given a sorted array and a target, return the index where target is or would be inserted. Asana asks this to confirm you can write a bug-free binary search — a building block for task-priority ordering in their backend.

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

Source citations

Public interview reports confirming this problem appears in Asana loops.

  • Glassdoor (2026-Q1)— Asana phone-screen variant.

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 complexity.

Constraints

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

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

Example 3

Input
nums = [1,3,5,6], target = 7
Output
4

Approaches

1. Linear scan

Return the first index where nums[i] >= target, or nums.length.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) if (nums[i] >= target) return i;
  return nums.length;
}

Tradeoff: Doesn't honor the O(log n) requirement.

2. Binary search lower-bound

Maintain lo, hi as the candidate range; lo converges to 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: Classic lower-bound binary search. The hi = nums.length init handles the 'insert at end' case naturally.

Asana-specific tips

At Asana, binary-search bugs are the #1 disqualifier here. Use the half-open interval [lo, hi) — it eliminates the off-by-one on the upper bound when inserting at the end. State your invariants out loud: 'lo never exceeds the answer, hi is always a valid upper bound.'

Common mistakes

  • Initializing hi = nums.length - 1 — fails when target is larger than all elements.
  • Using (lo + hi) / 2 in languages where it can overflow — use lo + (hi - lo) / 2.
  • Off-by-one in the inequality (< vs <=).

Follow-up questions

An interviewer at Asana may pivot to one of these next:

  • Return the upper bound instead of the lower bound.
  • Handle duplicates — return the first or last occurrence.
  • Binary search on a rotated sorted array (LC 33).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why initialize hi to nums.length, not nums.length - 1?

The half-open interval [lo, hi) makes 'insert at end' a valid answer. If hi = length - 1, you can't represent the 'insert past the last element' case.

Why is JS safe from (lo + hi) / 2 overflow?

JS numbers are 64-bit floats; you'd need arrays of ~9 * 10^15 elements to overflow. The defensive form is still good habit for cross-language portability.

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Asana interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →