Skip to main content

6. Search Insert Position

easyAsked at Salesforce

Find the index to insert a target value into a sorted array. Salesforce uses this to test whether you implement binary search with the correct boundary semantics — the same pattern their SOQL ORDER-BY range queries depend on.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Asked on Service Cloud backend onsites as a binary-search warmup.
  • Blind (2025-12)— Salesforce loves binary-search variants because their index lookups are sorted-range scans.

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) violates the O(log n) requirement explicitly stated in the problem. Salesforce will fail this immediately.

2. Binary search (lower bound)

Find the leftmost index i where nums[i] >= target. Lo/hi invariant: answer is always in [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: Lower-bound binary search. hi starts at nums.length (not length-1) so insertion at the end works naturally.

Salesforce-specific tips

Salesforce binary-search questions are graded heavily on boundary correctness — get hi = nums.length (not nums.length - 1) right and you signal you've internalized lower_bound semantics. Bonus signal: mention that this is equivalent to C++'s std::lower_bound or Python's bisect_left, which Salesforce engineers use daily for sorted-index lookups.

Common mistakes

  • Using hi = nums.length - 1 — fails when target should be inserted at the end.
  • Using lo <= hi instead of lo < hi with hi = nums.length — infinite loop or off-by-one.
  • Using nums[mid] <= target instead of < — gives upper_bound not lower_bound.

Follow-up questions

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

  • Return the upper-bound index instead (first index where nums[i] > target).
  • Search in a rotated sorted array (LC 33).
  • Find both the first and last index of target (LC 34).

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 nums.length (past the end). hi must be able to reach that value.

What's the difference between lower_bound and upper_bound?

lower_bound returns the first index with value >= target. upper_bound returns the first with value > target. Their difference is the count of equal elements.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →