Skip to main content

42. Find First and Last Position of Element in Sorted Array

mediumAsked at Salesforce

Find the first and last position of a target in a sorted array in O(log n). Salesforce uses this to test the lower_bound / upper_bound pattern, used in their SOQL index range queries.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce SOQL team uses lower/upper bound search in real production queries.
  • LeetCode Discuss (2025)— Tests dual binary search comfort.

Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non-decreasing array.
  • -10^9 <= target <= 10^9

Examples

Example 1

Input
nums = [5,7,7,8,8,10], target = 8
Output
[3,4]

Example 2

Input
nums = [5,7,7,8,8,10], target = 6
Output
[-1,-1]

Example 3

Input
nums = [], target = 0
Output
[-1,-1]

Approaches

1. Find target, then scan outward

Binary search for target, then linearly expand left and right.

Time
O(log n + k) where k = duplicates
Space
O(1)
function searchRange(nums, target) {
  let lo = 0, hi = nums.length - 1, found = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) { found = mid; break; }
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  if (found === -1) return [-1, -1];
  let l = found, r = found;
  while (l > 0 && nums[l - 1] === target) l--;
  while (r < nums.length - 1 && nums[r + 1] === target) r++;
  return [l, r];
}

Tradeoff: Degrades to O(n) when all elements are target. Salesforce will push for pure O(log n).

2. Two binary searches: lower_bound and upper_bound

Find leftmost index where nums[i] >= target (lower_bound). Find leftmost index where nums[i] > target (upper_bound). Range = [lower, upper - 1].

Time
O(log n)
Space
O(1)
function searchRange(nums, target) {
  const bound = (isLower) => {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] > target || (isLower && nums[mid] === target)) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  };
  const left = bound(true);
  if (left === nums.length || nums[left] !== target) return [-1, -1];
  const right = bound(false) - 1;
  return [left, right];
}

Tradeoff: Pure O(log n). The bound function unifies lower_bound and upper_bound by flipping a single condition. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses lower_bound / upper_bound throughout their indexed-range queries (e.g., 'count records where Date BETWEEN x AND y'). They grade on whether you separate the two boundary searches. Bonus signal: discuss the unified bound function — it's the cleanest implementation in JavaScript and Salesforce engineers use this exact pattern.

Common mistakes

  • Returning [found, found] for a single hit — works but misses the dual-bound pattern they want.
  • Off-by-one in upper_bound (forgetting to subtract 1 after finding upper boundary).
  • Not checking `nums[left] !== target` — returns wrong indices when target isn't present.

Follow-up questions

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

  • Search Insert Position (LC 35) — single bound search.
  • Count occurrences of target in O(log n) — same algorithm.
  • Generalize to range queries on indexed fields.

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 is the search range [lo, hi) and not [lo, hi]?

Because we're looking for an INDEX where insertion is possible, including past the end (hi = nums.length). hi is exclusive in the half-open range.

Why subtract 1 from upper_bound for the right index?

upper_bound returns the first index where value > target. The last index equal to target is therefore upper_bound - 1.

Practice these live with InterviewChamp.AI

Drill Find First and Last Position of Element in Sorted Array 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 →