Coding Interview: Find the First and Last Position with Binary Search

Problem and Applicable Context

Given an integer array nums sorted in non-decreasing order and an integer target, return the first and last indices of target. Return [-1, -1] when it is absent. The array may be empty and may contain duplicates, and the function must not mutate it. The required time complexity is O(log n) with O(1) extra space.

For example, nums = [1, 2, 2, 2, 3] and target = 2 returns [1, 3]; target = 4 returns [-1, -1]. A linear scan can produce the answer, but its O(n) worst case violates the requirement.

This question fits coding rounds for software engineering and algorithm roles. Amazon's current SDE II interview guide expects syntactically correct, scalable, robust, and well-tested code, and LeetCode maintains the same core problem. The real test is not memorizing two templates. It is defining the search boundary precisely enough that the loop condition, interval updates, and return value all follow one invariant.

What the Interviewer Is Evaluating

The first signal is whether the candidate recognizes that finding any occurrence is insufficient. An ordinary binary search that returns on equality does not guarantee the leftmost or rightmost occurrence. Finding one occurrence and then scanning outward still degrades to O(n) when every element equals the target.

The second signal is boundary semantics. A clean decomposition searches for two insertion points:

• lowerBound: the first position whose value is greater than or equal to target.
• upperBound: the first position whose value is strictly greater than target.

Python's official bisectleft and bisectright use these partition definitions. Once both points are correct, an existing target occupies [lowerBound, upperBound - 1].

The third signal is the loop invariant. With a half-open interval [left, right), an empty array naturally starts as [0, 0), and termination is left === right. Mixing a closed-interval rule with a half-open initialization, such as setting right to nums.length and later reading nums[right], causes out-of-bounds access or a non-terminating loop.

Finally, the interviewer looks for verification. A strong answer covers an empty array, one element, all duplicates, a target below the minimum, a target above the maximum, targets at both ends, and a missing target. It also explains why target + 1 is not a general upper-bound technique: it depends on a discrete numeric successor, creates an out-of-domain value at the largest safe integer, and does not extend to strings or custom comparators.

Clarifying Questions Before Answering

• Is the array already sorted? This prompt guarantees non-decreasing order. Sorting an unsorted input while

preserving original indices changes the data model and removes the O(log n) total bound.

• Do we return original or sorted indices? They are the same here because the input is already sorted.
• What represents absence? This prompt requires [-1, -1]; an insertion point is not automatically a match.
• Are duplicate values allowed? Yes. Duplicates are the reason boundary searches are needed.
• May the array be empty? Yes. A half-open implementation handles it without reading either endpoint.
• What is the numeric domain? Values are JavaScript safe integers. The solution does not compute target + 1, so

it does not manufacture an out-of-domain sentinel just to find a boundary.

• Must binary search be implemented? Yes for this interview exercise. In production, prefer a standard-library

function when its contract matches exactly.

• May the input be mutated? No, and neither boundary search needs to mutate it.

30-Second Answer Framework

“I would run two boundary searches instead of finding one occurrence and scanning. lowerBound searches the half-open interval [left, right) for the first value greater than or equal to target; upperBound finds the first value strictly greater than target. Each iteration uses middle = left + floor((right - left) / 2). If the midpoint is still on the target's left side, set left = middle + 1; otherwise retain the midpoint with right = middle. I first check whether the lower bound is out of range or not equal to the target. If it exists, the answer is [lower, upper - 1]. Two searches remain O(log n) with O(1) extra space.”

Step-by-Step Deep Dive

Step 1: Rewrite “first and last” as two partition points.

For nums = [1, 2, 2, 2, 3] and target = 2:

lowerBound = 1  // first nums[i] >= 2
upperBound = 4  // first nums[i] > 2
answer = [1, 4 - 1] = [1, 3]

This definition is easier to verify than “keep looking left” and “keep looking right.” The insertion points remain meaningful when the target is absent. For target = 4, both equal the array length 5, but that does not mean the target exists. The algorithm must separately check nums[lower] === target.

Step 2: Fix the half-open interval invariant.

At the start of every lowerBound iteration:

1. Every index below left contains a value strictly less than target.
2. Every index at or above right contains a value greater than or equal to target.
3. The unresolved candidate interval is [left, right).

Initially, left = 0 and right = nums.length; both outside regions are empty, so the invariant holds. If nums[middle] < target, the midpoint and everything to its left cannot be the answer, so set left = middle + 1. Otherwise, the midpoint might be the first valid position and must remain, so set right = middle.

Every iteration strictly shortens the interval. When left === right, no unresolved element remains. Everything on the left is smaller and everything on the right is greater than or equal to the target, so this position is the lower bound.

upperBound uses the same structure with a different partition:

1. Every index below left contains a value less than or equal to target.
2. Every index at or above right contains a value strictly greater than target.

It therefore moves left when nums[middle] <= target and otherwise moves right.

Step 3: Implement both boundary functions.

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

function upperBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] <= target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

The only difference is the comparison. Two clearly named functions are easier to explain in an interview than one function with an opaque Boolean switch, and they avoid inventing a complex generic abstraction for one use.

The midpoint is left + floor((right - left) / 2), so it does not add two large indices first. JavaScript runtime array limits make index overflow unlikely in this prompt, but the expression transfers safely to fixed-width integer languages.

Step 4: Combine the results and verify an actual match.

function searchRange(nums: number[], target: number): [number, number] {
  const first = lowerBound(nums, target);

  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  return [first, upperBound(nums, target) - 1];
}

The check order matters. Test first === nums.length before reading nums[first], so a position after the array is not treated as an element. Once first is known to match, the upper bound is at least first + 1, and subtracting one gives the last occurrence.

Do not replace the upper bound with lowerBound(nums, target + 1) - 1. Under this prompt's safe-integer constraint, it may still return the right boundary, but adding one to Number.MAXSAFEINTEGER leaves the domain in which exact integer arithmetic is guaranteed. If the input expands to arbitrary JavaScript Numbers, adjacent integers can also collapse under floating-point precision. Strings, BigInt values, and custom comparators have no universal “next value.” Searching directly for the first value strictly greater than the target expresses the complete contract.

Step 5: Prove the complexity.

Each loop reduces a candidate interval of length k to at most roughly k / 2, so each boundary function performs O(log n) comparisons. Two searches are still O(log n). The algorithm stores only a constant number of indices, uses O(1) extra space, and does not mutate the array.

Finding any occurrence and scanning outward visits all n elements for [2, 2, ..., 2], giving an O(n) worst case. A precomputed hash table can make repeated lookups fast, but construction costs O(n) time and space. It is useful only for many queries over the same static input and ignores the given sorted-order advantage.

Step 6: Validate with boundary cases and randomized differential tests.

At minimum, cover:

| Input | target | Expected | |---|---:|---:| | [] | 1 | [-1, -1] | | [5] | 5 | [0, 0] | | [5] | 4 | [-1, -1] | | [1, 2, 2, 2, 3] | 2 | [1, 3] | | [2, 2] | 2 | [0, 1] | | [1, 2, 3] | 0 | [-1, -1] | | [1, 2, 3] | 4 | [-1, -1] |

Then generate sorted arrays with duplicates and compare the result with the linear indexOf and lastIndexOf baseline. The linear approach does not meet the target complexity, but it is an excellent test oracle. Fixed cases check known boundaries, while randomized differential tests expose errors tied to particular duplicate counts or endpoints.

High-Quality Sample Answer

“The array is already sorted and the requirement is O(log n), so I would not find one target and scan outward; an all-duplicate array would become linear. I define the answer with two insertion points: the first value greater than or equal to the target, and the first value strictly greater than the target.

Both searches use the half-open interval [left, right). For the left boundary, the invariant says everything before left is smaller than the target and everything from right onward is greater than or equal to it. If the midpoint is smaller, the answer must be to the right, so I set left = middle + 1. Otherwise, the midpoint may be the answer, so I set right = middle. When they meet, that position is the lower bound. The upper bound changes only the condition: values less than or equal to the target move left.

I compute the lower bound first. If it equals the array length or does not contain the target, I return [-1, -1]. Otherwise, the right endpoint is the upper bound minus one. Empty input, a missing target, all duplicates, and matches at either endpoint all use the same logic.

Every iteration halves the interval, so two searches are still O(log n) and use O(1) extra space. I would verify fixed boundary cases and then compare random sorted arrays against indexOf and lastIndexOf. I would not use target + 1, because it invents a sentinel outside the stated domain and does not generalize to other ordered domains.”

Common Mistakes

• Finding any occurrence and scanning outward → an all-equal array becomes O(n) → binary-search the lower and upper bounds separately.
• Returning immediately on equality → the hit is arbitrary rather than leftmost or rightmost → retain the half that may still contain the boundary.
• Initializing right to the length and reading nums[right] → the half-open endpoint is not accessible → read only middle and terminate when both endpoints meet.
• Updating with left = middle → a two-element interval may never shrink → use middle + 1 when excluding the midpoint.
• Returning an insertion point for a missing target → a valid insertion position is not a match → check bounds and nums[first] !== target.
• Using target + 1 for the right boundary → it relies on an out-of-domain or nonexistent successor → implement the first position strictly greater than the target.
• Mixing closed and half-open templates → initialization, loop condition, and updates conflict → write the interval semantics and invariant before the code.
• Testing only duplicates in the middle → empty input, endpoints, and misses can still fail → add a boundary table and randomized differential tests.
• Claiming sort-then-search is still O(log n) → sorting dominates the total cost → use the sorted-input guarantee or recalculate the full complexity.

Follow-Up Questions and Responses

Follow-up 1: If you only need to test whether the target exists, do you need two searches?

No. Run one lower-bound search and check that its position is in range and equals the target. That remains O(log n). If a standard library provides exactly this contract, production code may use it directly. Two searches are necessary only to obtain both ends of a duplicate range.

Follow-up 2: How would you return the number of occurrences?

When the target exists, the count is upperBound - lowerBound. When it is absent, the two insertion points are equal, so the difference is also zero. A count-only function therefore does not even need to read an array element. The formula works because every element between the two boundaries equals the target.

Follow-up 3: What changes if the array is sorted in descending order?

Reverse the invariant and comparisons. A descending lower bound can mean the first value less than or equal to the target, and the other boundary is the first value strictly less than it. Do not reverse only the final interpretation while keeping the original comparisons. Define the partition predicate first, then update the interval from its truth value.

Follow-up 4: What if elements are objects and the search uses one field?

Search a sorted comparison key, such as createdAt. If key extraction is expensive across repeated queries, keep a precomputed key array; the Python documentation likewise recommends caching or precomputing costly keys. The object sequence must not be mutated during the search, or the sorted invariant no longer holds.

Follow-up 5: What if the data is in a database with an ordered index rather than in memory?

Do not translate application binary search into many remote queries. Let the database index locate the range, such as the minimum and maximum stable sort keys equal to the target or an index range scan. One network round trip per binary search iteration turns O(log n) comparisons into repeated high-latency calls and may observe different snapshots during concurrent writes.

Follow-up 6: How does this template extend to “minimum feasible answer” problems?

Define a monotonic predicate, such as every capacity below x being infeasible and every capacity from some point onward being feasible. Then lower-bound the first true predicate over an implicit answer space, replacing nums[middle] < target with !feasible(middle). The predicate must be proven to transition from false to true only once; if truth values alternate, binary search has no correctness basis.