Skip to main content

6. Search Insert Position

easyAsked at Adobe

Given a sorted array and a target, return the index where the target would be inserted to keep the array sorted. Adobe uses this to test whether you can write boundary-correct binary search — the same primitive used in z-order insertion of layers.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe Document Cloud tests this as a binary-search litmus.
  • LeetCode Discuss (2025-10)— Common Adobe SDE-II phone screen problem.

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 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: Violates the O(log n) constraint. Mention only as the warm-up baseline.

2. Binary search (lower bound)

Standard binary search; when not found, lo points to the insertion index.

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

Tradeoff: Logarithmic time. The 'hi = nums.length' (one past the end) and 'lo < hi' (strict) form is the lower-bound idiom — when the target is missing, lo lands exactly on the insertion index.

Adobe-specific tips

Adobe pays attention to the boundary form: hi = nums.length or hi = nums.length - 1? lo < hi or lo <= hi? Pick one form and stay consistent. They'll often follow up with 'now find the upper bound' to test if you really understand the invariants. The lower-bound idiom is what backs std::lower_bound in C++ and is used in z-order insertion of layers.

Common mistakes

  • Using hi = nums.length - 1 with lo <= hi but then returning lo without handling the 'past the end' insertion case.
  • Off-by-one in 'lo = mid + 1' vs 'hi = mid' — these are not interchangeable.
  • Computing mid as (lo + hi) / 2 — overflow risk on huge arrays in fixed-width languages.

Follow-up questions

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

  • Find the upper bound — index of first value > target.
  • Find both bounds — gives the range of equal values (LC 34).
  • Search in a rotated sorted array (LC 33) — extends binary search.

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 = nums.length and not nums.length - 1?

Because the insertion index can be one past the last element. Using nums.length lets lo legally reach that position. The strict 'lo < hi' loop guard then terminates cleanly.

Why is lo + ((hi - lo) >> 1) safer than (lo + hi) / 2?

It avoids integer overflow when lo + hi exceeds the max safe integer. JavaScript is forgiving here but it's a habit worth keeping for C++/Java versions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →