Skip to main content

6. Search Insert Position

easyAsked at Reddit

Find the index where a target should be inserted in a sorted array. Reddit uses this binary-search variant to gate whether candidates can implement lower_bound correctly — critical for ranked feed insertion when a new post enters Hot.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit feed-team phone screen on binary-search edge cases.
  • Blind (2025-09)— Reported alongside ranked-feed insertion follow-ups.

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 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: Fails the explicit O(log n) requirement.

2. Binary search lower_bound (optimal)

Maintain [lo, hi] inclusive range. When loop exits, lo is the insert position.

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. Use hi = nums.length (exclusive) so insertion-at-end works.

Reddit-specific tips

Reddit interviewers grade for the lower_bound pattern over the 'two-cases' textbook binary search. Bonus signal: mention that ranked feeds use this to insert a new post into a sorted-by-score list, and explain why hi=nums.length (not n-1) is essential.

Common mistakes

  • Using hi = nums.length - 1 — breaks when target > all elements.
  • Returning mid when lo < hi — premature exit; the insert position may shift.
  • Using (lo + hi) / 2 in languages that overflow (use lo + (hi - lo) / 2 or unsigned shift).

Follow-up questions

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

  • First and last position of element (LC 34).
  • What if duplicates are allowed? lower_bound still works; describe upper_bound for the range.
  • 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 lo < hi and not lo <= hi?

When hi is exclusive (n, not n-1), lo == hi means the search range is empty, so lo is the answer.

What is the invariant?

Everything in [0, lo) is < target; everything in [hi, n) is >= target. When lo == hi, that's the boundary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →