Skip to main content

6. Search Insert Position

easyAsked at Intuit

Find the index where a target should be inserted into a sorted array to keep it sorted. Intuit asks this as a binary-search warm-up — useful for tax-bracket lookup: 'which bracket does this income fall into?'

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— TurboTax tax-engine SWE screen, explicitly tied to tax-bracket lookup.
  • LeetCode Discuss (2025-12)— Intuit phone-screen problem from 2025 hiring round.

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

Walk left to right; return the first index where nums[i] >= target.

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: Violates the O(log n) requirement explicitly stated in the problem.

2. Binary search lower-bound (optimal)

Classic lower-bound binary search. Maintain [lo, hi). When you exit, lo is 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: O(log n). The half-open [lo, hi) invariant handles both 'found' and 'insert' uniformly — no separate branch.

Intuit-specific tips

Intuit interviewers love this for tax-bracket-lookup framing: given sorted bracket cutoffs [9950, 40525, 86375, 164925, ...], find which bracket income x belongs to. The off-by-one fix (use lower-bound, not upper-bound) determines whether income exactly at a cutoff goes into the higher or lower bracket — a real edge case the IRS specifies. Bonus signal: discuss the half-open invariant.

Common mistakes

  • Using (lo + hi) / 2 without |0 or Math.floor — works in JS for small numbers but lacks the >>>0 safety against overflow in other languages.
  • Closed-interval binary search [lo, hi] with subtle off-by-one in termination.
  • Returning -1 when not found instead of the insertion index.

Follow-up questions

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

  • Find first AND last position of target (LC 34).
  • Lookup tax bracket given sorted cutoff array — same algorithm, different framing.
  • Search in 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 use [lo, hi) instead of [lo, hi]?

Half-open makes the loop invariant easier: 'the answer is in [lo, hi)'. When lo == hi the interval is empty and lo is the insertion point. Closed intervals work too but have more edge cases.

Why >>> 1 instead of / 2?

>>> 1 is integer-only and guards against overflow in lo + hi (less relevant in JS but a habit from C/Java). Math.floor((lo+hi)/2) is also fine.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →