Skip to main content

6. Search Insert Position

easyAsked at Datadog

Given a sorted array and a target, return the index where the target would be inserted. Datadog uses this as the bedrock for binary-search-on-time questions — every metric query that bisects timestamps uses this pattern.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog reports cite this as the binary-search warmup before TSDB-style problems.
  • Blind (2025-11)— Often the second question of a Datadog onsite 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 until you find a value >= 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: O(n) — fine for a few thousand entries but blows up at TSDB scale (millions of timestamps per series).

2. Binary search (optimal)

Maintain [lo, hi) where the answer lies. Halve until lo == 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. The half-open invariant [lo, hi) makes the off-by-one logic clean — this is the exact pattern used in Datadog's TSDB seek path.

Datadog-specific tips

Datadog will reuse this primitive in 'find the index of a timestamp in a sorted block' or 'binary search on a column-store row index.' Articulate the half-open invariant — lo == hi == answer — because the closed-interval variant has off-by-one bugs that won't survive code review at Datadog.

Common mistakes

  • Using (lo + hi) / 2 in some languages — integer overflow. In JS, '(lo + hi) >>> 1' is the canonical safe form.
  • Mixing closed-interval [lo, hi] and half-open [lo, hi) conventions in one function — produces off-by-one bugs.
  • Returning -1 when not found instead of the insertion point.

Follow-up questions

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

  • Find First and Last Position (LC 34) — two binary searches.
  • Search in Rotated Sorted Array (LC 33).
  • Binary search on a column-store TSDB block — return the row index for a timestamp.

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]?

With half-open, the answer is always lo and the loop terminates at lo == hi. Fewer special cases for empty arrays and beyond-the-end inserts.

What if duplicates exist?

The problem assumes distinct values. With duplicates, you'd return either the leftmost or rightmost matching index — a separate variant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →