Skip to main content

6. Search Insert Position

easyAsked at Palantir

Find the index where a target should be inserted in a sorted array. Palantir uses this as a binary-search litmus test before harder lower-bound problems on time-series telemetry indices.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-12)— Asked in Palantir Foundry FDE phone screens.
  • Blind (2026-Q1)— Cited as warm-up before time-range index lookup question.

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 until you find target or a larger value.

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

Tradeoff: Violates the O(log n) requirement.

2. Binary search (lower bound)

Standard half-open interval [lo, hi). The invariant is: nums[lo-1] < target <= nums[hi].

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: Logarithmic, no off-by-one. The half-open interval is the safest binary search template — same one used in C++ std::lower_bound.

Palantir-specific tips

Palantir grades binary-search problems on whether you state the loop invariant explicitly. Mention: 'this is lower_bound; on exit, lo points to the first index where nums[i] >= target.' If you can adapt the same template to upper_bound (>) without rewriting, that's the bonus signal. This pattern shows up daily in Foundry when you binary-search a time index to find the first event at or after a timestamp.

Common mistakes

  • Using lo <= hi with hi = nums.length-1 — works but more error-prone than the half-open version.
  • Computing mid as (lo+hi)/2 — overflows in languages with bounded int (use lo + (hi-lo)/2 or >>> 1).
  • Returning mid when nums[mid] >= target instead of continuing — gives wrong answer on duplicates (but problem says distinct, so it accidentally passes).

Follow-up questions

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

  • What if the array has duplicates? (Lower bound finds the FIRST occurrence; upper bound finds the position AFTER the last.)
  • Find the first and last position of target (LC 34).
  • 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 half-open [lo, hi) instead of closed [lo, hi]?

It removes the +1/-1 off-by-one issues. The exit condition lo == hi naturally points to the insertion position with no extra logic.

What does >>> 1 do?

It's an unsigned right shift, equivalent to dividing by 2 but avoiding any sign-bit issues on huge arrays. Most interviewers accept Math.floor((lo+hi)/2) too.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →