First and Last Position in TypeScript: Search past the Match

Finding a matching value can be the wrong moment to stop searching. In a sorted array such as [‑4, 2, 2, 2, 6, 9], an ordinary binary search might return index 2 for the target 2. That is a valid match, but it doesn't tell us where the run of twos begins or ends.
LeetCode's First and Last Position problem asks for both endpoints, with [‑1, ‑1] for an absent target. The array can contain duplicates, and the required runtime is still logarithmic. The extra work is deciding which matching position we mean, rather than merely finding one.
Why Walking Outwards Loses the Guarantee
A tempting solution finds any match with binary search, then walks left and right whilst adjacent values are equal. It works, and on a short run it looks perfectly respectable. An array containing a hundred thousand copies of the target is less impressed. Walking across that run takes linear time.
We need to use ordering for both endpoints. I'll find the first position whose value is at least the target, then the first position whose value is greater than it. These are usually called the lower bound and upper bound. The second position is one past the final match, which gives us a convenient way to describe an empty run too.
My binary search foundations article uses an inclusive right endpoint and returns when it finds a match. Here I'm deliberately changing the interval convention and the stopping condition. Mixing one version's loop with another version's pointer updates is an efficient way to manufacture an off‑by‑one bug.
Search for the First True Position
For the lower bound, read the sorted array as answers to "is this value at least the target?" With target 2, our example becomes false, true, true, true, true, true. We want the first true position. For the upper bound, the question is "is this value greater than the target?", producing false, false, false, false, true, true.
Each predicate changes from false to true at most once. It can also be false everywhere or true everywhere. The code needs to handle those cases without inventing an element outside the array.
I use a half‑open interval: left is included and right is excluded. Initially they are zero and the array length. Positions below the left endpoint have already been proved false; positions at or above the right endpoint have been proved true, if those positions exist. The unresolved indices are between the two endpoints.
When the pointers meet, that index is the answer. It can equal the array length, meaning there was no true position. That is an insertion position, not an instruction to read beyond the array.
Two Comparisons, One Search Shape
The lower‑bound search moves right past values smaller than the target. Equality stays on the left‑hand search side, because an earlier equal value might still exist. The upper‑bound search moves past equality too. That single difference is the purpose of keeping the helpers separately named.
export const lowerBound = (
values: readonly number[],
target: number,
): number => {
let left = 0;
let right = values.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (values[middle]! < target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
};
export const upperBound = (
values: readonly number[],
target: number,
): number => {
let left = 0;
let right = values.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (values[middle]! <= target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
};
export const searchRange = (
values: readonly number[],
target: number,
): [number, number] => {
const first = lowerBound(values, target);
if (first === values.length || values[first] !== target) {
return [-1, -1];
}
return [first, upperBound(values, target) - 1];
};The input is read‑only, and neither helper sorts, slices, nor changes it. The non‑null assertions follow from the loop: whilst the left endpoint is smaller than the excluded right endpoint, the rounded‑down midpoint is a valid index. As with the foundation example, the runtime input must be a dense, sorted array of finite numbers.
I could combine the helpers behind a boolean argument, but then every call would need an explanation of what that boolean means. Two short named searches make the equality rule visible where I'm most likely to review it. They also give us independently testable operations for insertion positions and counts.
Following a Run of Duplicates
For [‑4, 2, 2, 2, 6, 9], the lower‑bound interval starts at [0, 6). Its midpoint is index 3, containing 2. Equality qualifies, so the right endpoint becomes 3. Next we inspect index 1, also 2, and move the right endpoint to 1. Index 0 contains ‑4, so the left endpoint advances to 1. Both endpoints are now 1: that is the first qualifying position.
The upper‑bound search starts again at [0, 6). At index 3, equality does not qualify, so the left endpoint becomes 4. Index 5 contains 9, moving the right endpoint to 5. Index 4 contains 6, moving it to 4. The result is 4, so the last matching index is 3.
Our answer is [1, 3]. Subtracting the lower bound from the upper bound also gives the number of matches, three, without walking through them. Keeping the excluded endpoint until the final subtraction makes that relationship pleasantly unremarkable.
console.log(searchRange([-4, 2, 2, 2, 6, 9], 2)); // [1, 3]
console.log(searchRange([-4, 2, 2, 2, 6, 9], 3)); // [-1, -1]
console.log(searchRange([2, 2, 2], 2)); // [0, 2]
console.log(searchRange([2], 2)); // [0, 0]
console.log(searchRange([], 2)); // [-1, -1]An Insertion Position is Not Proof of a Match
Searching the same array for 3 produces a lower bound of 4, where the value is 6. That is the correct insertion position, but there are no threes. The equality check in searchRange is essential before interpreting the bounds as a matching run.
For an empty array, both initial endpoints are zero and no midpoint is read. For a target larger than every value, the lower bound equals the length. The short‑circuit check handles that before reading the indexed value. If every element matches, the lower bound is zero and the upper bound is the length, so both outer edges work without a special duplicate case.
I also avoid calculating an upper bound by searching for the target plus one. That works within this problem's integer limits, but it embeds a successor assumption the greater‑than comparison doesn't need. If these helpers are later adapted to a different ordered domain, their names and comparisons still say what they mean.
The Proof and the Cost
When a midpoint fails the predicate, all earlier values fail too, so advancing past it preserves the first possible true position. When it qualifies, everything to its right qualifies, so we keep searching the earlier positions by moving the excluded endpoint to the midpoint. The endpoint itself can be the answer even though it is no longer an unresolved array index.
Every iteration reduces the unresolved interval, and its size is at most halved, rounded down. Two searches therefore take O(log n) time for non‑empty input, with O(1) auxiliary space. The returned pair is constant‑sized. No amount of duplication changes those bounds, and the array remains untouched.
My Binary Search Boundary Lab compares both helpers and the final range with linear oracles across exhaustive small sorted arrays, plus larger repeated‑value cases. It checks absent targets between runs as well as at the extremes. Changing just one equality comparison should produce a small failing example, which is more useful than a reassuring test on distinct numbers.
This first‑true‑position view also appears in my Koko Eating Bananas walkthrough. The predicate there measures whether a speed is sufficient. My rotated‑array article needs a different ordering argument before it can discard a side. Here the whole array is already ordered; the detail worth keeping is what happens after equality. We have found a candidate, and we still have a question to answer.