Skip to main content

6. Search Insert Position

easyAsked at ServiceNow

Find the index where a target should be inserted in a sorted array to keep it sorted. ServiceNow uses this to verify binary-search fluency — the same primitive their SLA timer scheduler uses to insert new deadlines into an ordered heap.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q1)— ServiceNow phone screens use this to probe binary-search invariants.
  • LeetCode Discuss (2025-11)— Multiple posts cite this as a 30-minute screen problem at ServiceNow.

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. If none, return 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: Violates the explicit O(log n) requirement. Mention only as the obvious-but-wrong answer.

2. Binary search for lower bound

Maintain [lo, hi]. Each step: mid = (lo+hi) >> 1. If nums[mid] < target, lo = mid+1; else hi = mid-1. Final answer is lo.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo;
}

Tradeoff: Logarithmic — fits the requirement. The trick is returning lo (not mid) at the end, which is the insert position.

ServiceNow-specific tips

ServiceNow grades binary search by whether you can state the loop invariant before coding — they want 'target lives in [lo, hi]' explicitly. Bonus signal: mention that the lower-bound flavor is what their workflow scheduler uses to slot a new SLA escalation into the timer queue.

Common mistakes

  • Off-by-one on the boundary: lo < hi vs. lo <= hi confuses the final position.
  • Returning hi or mid at the end — only lo gives the correct insert position.
  • Integer overflow on (lo+hi)/2 in languages with fixed-width ints (use lo + ((hi-lo)>>1)).

Follow-up questions

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

  • Find First and Last Position of Element in Sorted Array (LC 34).
  • Search in Rotated Sorted Array (LC 33).
  • What if duplicates were allowed? (Lower-bound variant.)

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 return lo and not hi?

When the loop exits, lo > hi. lo is the first index whose value is >= target (or nums.length if all elements are smaller), which is precisely the insert position.

Could the loop be `while (lo < hi)`?

Yes — but then you'd shrink hi to mid instead of mid-1, and the final answer is still lo. Both are correct; pick one style and be consistent.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →