Skip to main content

6. Search Insert Position

easyAsked at Workday

Given a sorted array and a target, return the index where the target is found or would be inserted. Workday uses this to test binary-search hygiene for slot-aware pay-grade insertion into compensation bands.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026)— Workday compensation-team phone screen.
  • LeetCode Discuss (2025)— Workday SDE2 round-1.

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 until first index where nums[i] >= target.

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

Tradeoff: Easy to write, but the prompt explicitly demands O(log n).

2. Binary search (lower bound)

Standard lower-bound binary search. Return lo at the end — it lands on 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: hi = length (not length - 1) so the answer can be N (insert past end). Standard lower-bound pattern.

Workday-specific tips

Workday grades binary search on three things: half-open interval discipline ([lo, hi) where hi = length), integer-overflow safety with (lo + hi) >>> 1, and recognizing lower-bound vs upper-bound. State which variant you're writing before you code.

Common mistakes

  • Setting hi = nums.length - 1 — then you can't return nums.length for past-end inserts.
  • Using (lo + hi) / 2 — fine in JS but signals you'd write a bug in Java/C++.
  • Off-by-one: lo = mid instead of mid + 1 causes infinite loops.

Follow-up questions

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

  • First Bad Version (LC 278) — same lower-bound pattern.
  • Find First and Last Position of Element in Sorted Array (LC 34).
  • What if duplicates are allowed?

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 hi = length, not length - 1?

Half-open interval [lo, hi) — hi represents 'one past last possible answer'. Since the answer can be N (insert past end), hi must start at N.

Why (lo + hi) >>> 1?

Unsigned right shift avoids overflow in Java/C++ if lo + hi > INT_MAX. In JS the practical difference is nil but it signals discipline.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →