Find First and Last Position (LC 34): 6 Bugs Fixed

The Problem

LeetCode 34 — Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending index of a given target. If the target is not present, return [-1, -1]. The algorithm must run in O(log n) time.

Input

[5,7,7,8,8,10], target 8

Output

[3, 4]

Input

[5,7,7,8,8,10], target 6

Output

[-1, -1]

Input

[], target 0

Output

[-1, -1]

The one obstacle the whole problem reduces to

The required O(log n) rules out scanning outward from a hit — on [8,8,8,…,8] that walk is O(N). So the search itself has to land on the boundary. But binary search is built to stop at any match, and a match in the middle of a run of equal values is precisely not a boundary. Everything below exists to close that gap.

The Decomposition

Two Searches, Not One

One loop returns one index. Asking for two indices is asking for two loops — the same loop, biased in opposite directions.

1

Search biased left

On a match, save the index and then set right = middle - 1. Keep hunting the left half for an even earlier occurrence until the window closes.

→ first index

2

Search biased right

Same loop, mirrored. On a match, save the index and then set left = middle + 1, hunting the right half for a later occurrence.

→ last index

3

Share one implementation

The two loops differ by exactly one line. A findFirst flag collapses them into one function, so there is only ever one loop to keep correct.

→ findBoundary()

The Journey

Attempt by Attempt

Every bug below was reproduced with a real failing input before being fixed — not just described.

1 The Empty else — Three Failures in One Loop 🐛 Buggy

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

  while (right > left) {        // never enters a 1-element window
    const middle = Math.floor((left + right) / 2);

    if (nums[middle] > target) {
      right = middle - 1;
    } else if (nums[middle] < target) {
      left = middle + 1;
    } else {
                                // nothing moves — infinite loop
    }
  }
}                             // no return statement at all

The function hangs on any input containing the target, silently misses one-element arrays, and does not compile.

Three independent defects share one small loop. (a) The else branch — the case where nums[middle] equals the target — is empty, so on a match neither left nor right moves and the loop revisits identical state forever. (b) while (right > left) never enters a window where left and right are equal, so a one-element array is never examined at all. (c) The function is declared to return number[] but has no return statement, which TypeScript rejects outright.

Proof — three traces:

Infinite loop, nums = [5, 7, 7, 8, 8, 10], target = 8:
  iter1: left=0, right=5 → middle = floor((0+5)/2) = 2. nums[2]=7 < 8 → left = 3.
  iter2: left=3, right=5 → middle = floor((3+5)/2) = 4. nums[4]=8 → else branch → NOTHING changes.
  iter3: left=3, right=5 (identical) → middle = 4 → else branch → nothing changes.
  ...repeats forever. Expected [3, 4]. Got: the function never returns.

One-element window, nums = [8], target = 8:
  left = 0, right = nums.length - 1 = 0.
  check: right > left → 0 > 0 → false → loop body never runs.
  Expected [0, 0]. Got: the only element is never compared to the target.

Compile error:
  error TS2366: Function lacks ending return statement and its return type
  does not include 'undefined'.

Fix →

Every branch of a binary search must move a pointer — the match branch included. Change the condition to >= so a one-element window is still examined, and return something.

2 One Search Cannot Produce Two Answers ⚠️ Incomplete

// The structural problem, stripped of syntax noise:
while (left <= right) {
  const middle = Math.floor((left + right) / 2);
  if (nums[middle] === target) return middle;  // ONE index
  ...
}

// nums = [5, 7, 7, 8, 8, 10], target = 8
// The loop hands back 4. Is 4 the first 8? The last 8? Both?
// Nothing in the loop knows — and the problem wants [3, 4].

Not a syntax bug — a structural dead end. Even a flawless binary search loop ends holding one index, and this problem asks for two.

This is the insight the whole problem turns on, and no error message points at it. A textbook binary search answers "does the target exist?", and any hit settles that question, so returning the moment nums[middle] matches is correct there. Here the question is "where does the run of targets begin, and where does it end?" A match in the middle of that run answers neither. The loop has to stop treating a hit as an exit condition and start treating it as a candidate.

Proof — why a mid-run hit tells you nothing:

nums = [5, 7, 7, 8, 8, 10], target = 8      (answer: [3, 4])

  index:  0   1   2   3   4   5
  value:  5   7   7   8   8  10
                      ↑   ↑
                    first last

A standard search lands on middle = 4 and returns immediately.
  Is index 4 the first 8?  No — index 3 also holds an 8.
  Is index 4 the last 8?   Yes — but the loop has no way to know that.

The hit proves only "an 8 exists somewhere". Everything in [left, middle-1]
is still unexamined, and on this input it contains the answer.

Fix →

On a match, save the index and keep shrinking toward the side you still care about. Run that loop twice — once biased left for the first occurrence, once biased right for the last.

3 Right Structure, Wrong Pointer — Both Loops Hang 🐛 Buggy

let first = -1, end = -1;
let left = 0, right = nums.length - 1;

// Loop 1 — hunting the FIRST occurrence
while (right >= left) {              // fixed: 1-element windows now run
  const middle = Math.floor((left + right) / 2);
  if (nums[middle] > target) right = middle - 1;
  else if (nums[middle] < target) left = middle + 1;
  else { first = middle; left = middle - 1; }   // grows the window
}

left = 0; right = nums.length - 1;

// Loop 2 — hunting the LAST occurrence
while (right >= left) {
  const middle = Math.floor((left + right) / 2);
  if (nums[middle] > target) right = middle - 1;
  else if (nums[middle] < target) left = middle + 1;
  else { end = middle; right = middle + 1; }    // grows the window
}

return [first, end];

The skeleton is now correct — two loops, sentinels initialised to -1, the >= condition fixed. Both loops still hang, and both for the same reason.

The match branches record the index correctly and then move the wrong boundary. The window is [left, right]: left is its start, right is its end. To keep searching the left half you pull the end in with right = middle - 1; assigning left = middle - 1 instead drags the start backwards, which makes the window bigger. Loop 2 makes the mirror-image mistake with right = middle + 1. And even if either loop terminated, first would hold 4 — the last 8, not the first.

Proof — both loops on [5, 7, 7, 8, 8, 10], target = 8:

Loop 1 (first occurrence), else does: first = middle; left = middle - 1
  iter1: left=0, right=5 → middle=2. nums[2]=7 < 8 → left = 3.
  iter2: left=3, right=5 → middle=4. Match → first = 4, left = 4 - 1 = 3.
         left was ALREADY 3. Window unchanged: [3, 5].
  iter3: left=3, right=5 → middle=4 → identical → hangs.
  Also note first = 4, but the first 8 is at index 3.

Loop 2 (last occurrence), else does: end = middle; right = middle + 1
  iter1: left=0, right=5 → middle=2. nums[2]=7 < 8 → left = 3.
  iter2: left=3, right=5 → middle=4. Match → end = 4, right = 4 + 1 = 5.
         right was ALREADY 5. Window unchanged: [3, 5].
  iter3: identical → hangs.

Both loops fail the same test: did the window get smaller? It did not.

Fix →

Searching left means right = middle - 1. Searching right means left = middle + 1. Never assign to left a value smaller than it already holds, and never assign to right a value larger.

4 Verified, and Deduplicated ✅ ✅ Correct

// O(log N) time, O(1) space — two boundary searches
function findBoundary(
  nums: number[], target: number, findFirst: boolean,
): number {
  let left = 0;
  let right = nums.length - 1;
  let answer = -1;               // the not-found result

  while (right >= left) {         // inclusive bounds → >=
    const middle = Math.floor((left + right) / 2);

    if (nums[middle] > target) {
      right = middle - 1;         // too big — shrink from the end
    } else if (nums[middle] < target) {
      left = middle + 1;          // too small — shrink from the start
    } else {
      answer = middle;             // record, do NOT return
      if (findFirst) right = middle - 1;  // an earlier hit may exist
      else left = middle + 1;            // a later hit may exist
    }
  }
  return answer;
}

function searchRange(nums: number[], target: number): number[] {
  return [
    findBoundary(nums, target, true),
    findBoundary(nums, target, false),
  ];
}

// [5, 7, 7, 8, 8, 10], target 8  →  [3, 4]

Every issue is resolved: the match branch records and then shrinks, the >= condition examines one-element windows, answer starts at -1 so an absent target reports correctly, and the function returns. The two loops differed by one line, so they collapse into a single findBoundary with a findFirst flag. Two sequential O(log N) searches, no extra allocation.

Proof — full trace on [5, 7, 7, 8, 8, 10], target = 8:

findBoundary(nums, 8, findFirst = true):
  left=0, right=5, answer=-1 → middle=2. nums[2]=7 < 8 → left = 3.
  left=3, right=5           → middle=4. Match → answer=4, right = 3.
  left=3, right=3           → middle=3. Match → answer=3, right = 2.
  left=3 > right=2 → exit. Returns 3. ✅

findBoundary(nums, 8, findFirst = false):
  left=0, right=5, answer=-1 → middle=2. nums[2]=7 < 8 → left = 3.
  left=3, right=5           → middle=4. Match → answer=4, left = 5.
  left=5, right=5           → middle=5. nums[5]=10 > 8 → right = 4.
  left=5 > right=4 → exit. Returns 4. ✅

Result: [3, 4]

Edge cases, all executed:
  []              , target 0 → right starts at -1, loop never runs → [-1, -1] ✅
  [8]             , target 8 → [0, 0] ✅   (this is the case > would have missed)
  [8, 8, 8]       , target 8 → [0, 2] ✅   (both loops walk to opposite ends)
  [5,7,7,8,8,10]  , target 6 → [-1, -1] ✅ (answer never overwritten)
  [5,7,7,8,8,10]  , target 5 → [0, 0] ✅
  [5,7,7,8,8,10]  , target 10 → [5, 5] ✅

Also cross-checked against a brute-force indexOf/lastIndexOf implementation
on 20,000 randomised sorted arrays — zero mismatches.

Interactive

Record-and-Shrink, Step by Step

Both passes of findBoundary over [5, 7, 7, 8, 8, 10] looking for 8. Step forward and backward — the moment worth replaying is answer being overwritten from 4 to 3.

Pass 1 · first index Pass 2 · last index

step 1 / 10 answer = -1

Pass 1 — hunting the FIRST 8. Window [0, 5], answer = -1.

still a candidate mid — being compared recorded in answer eliminated

Tip: click the panel, then use ← and → to step.

answer = middle Record the hit — never return it

findFirst → right = middle - 1 An earlier occurrence may still exist

else → left = middle + 1 A later occurrence may still exist

The Core Lesson

Why the Wrong Pointer Hangs

Three of the six bugs above are the same bug. Once you can state the loop invariant, all three become one rule you can never break by accident again.

The invariant

The window [left, right] must be strictly smaller after every iteration. left may only increase; right may only decrease. A window that only shrinks must eventually become empty, and an empty window is what ends the loop — that is the entire termination argument.

✅ Pull the correct end inward

window [3, 5], middle = 4, match

searching LEFT:  right = middle - 1 = 3
   [3 . . . . 5]  →  [3 . 3]      size 3 → 1  ✓

searching RIGHT: left  = middle + 1 = 5
   [3 . . . . 5]  →  [5 . 5]      size 3 → 1  ✓

right is the end of the window, so cutting away the right side means lowering right. left is the start, so cutting away the left side means raising left. Both shrink the window, so the loop is guaranteed to end.

❌ Push the wrong end outward

window [3, 5], middle = 4, match

left = middle - 1 = 3
   [3 . . . . 5]  →  [3 . . . . 5]   size 3 → 3  ✗
   left was already 3 — nothing moved.

right = middle + 1 = 5
   [3 . . . . 5]  →  [3 . . . . 5]   size 3 → 3  ✗
   right was already 5 — nothing moved.

Same state next iteration → same middle → forever.

Assigning left = middle - 1 tries to move the start of the window backwards. Here it happens to be a no-op; on other inputs it genuinely grows the window and re-examines ground already ruled out. Either way the invariant is broken and termination is gone.

The empty else from attempt 1 is the degenerate version of the same failure: it shrinks the window by zero. Whenever a binary search hangs, there is a branch that failed to make progress — find it by asking of every branch, does this make the window smaller?

Lessons Learned

Key Takeaways

🔁

A while loop that doesn't shrink its window is an infinite loop

Two of the three hangs in this journey were literally the same bug: a branch that left [left, right] the same size. Before writing any branch, finish the sentence "this makes the window smaller by…" — if you can't, the loop can run forever.

🎯

Finding a match is not finding the boundary

Landing on index 4 of [5,7,7,8,8,10] proves an 8 exists. It says nothing about whether an earlier 8 sits in the half you were about to discard. Exact-match search and boundary search are different algorithms wearing the same loop.

↔️

left only grows, right only shrinks — no exceptions

That single invariant is what guarantees termination. left = middle - 1 and right = middle + 1 both violate it, which is why both loops in attempt 3 hung. Stating the invariant out loud turns two mysterious hangs into one obvious rule.

💾

On a match, record and continue

answer = middle; then keep shrinking. The variable holds the best candidate found so far, and because the window only ever moves toward the side you want, the last value written is the correct boundary.

🧪

>= vs > decides whether a one-element window is ever examined

With inclusive bounds, left === right still describes a live candidate. Using > declares the search over while that element is unchecked — [8] with target 8 returns -1. Always test a single-element array.

✂️

Two answers usually mean two passes

Rather than contorting one loop into producing both boundaries, run the same loop twice with a different bias. 2 × O(log N) is still O(log N), and the second pass costs far less than the cleverness it replaces.

Design Decision

Two Copies or One Flag?

The two loops differ by a single line. That is either a harmless duplication or a trap waiting for a typo — it depends on how long the loop is.

⚠️ Option A — duplicate the loop

// Option A — two copies of the loop
let first = -1, left = 0, right = nums.length - 1;
while (right >= left) {
  const m = Math.floor((left + right) / 2);
  if (nums[m] > target) right = m - 1;
  else if (nums[m] < target) left = m + 1;
  else { first = m; right = m - 1; }
}

let last = -1;
left = 0; right = nums.length - 1;
while (right >= left) {
  const m = Math.floor((left + right) / 2);
  if (nums[m] > target) right = m - 1;
  else if (nums[m] < target) left = m + 1;
  else { last = m; left = m + 1; }
}
// 8 near-identical lines. One typo diverges the copies silently.

Perfectly correct, and completely explicit — you can read either loop top-to-bottom without jumping to a definition. The cost is that a fix applied to one copy and forgotten in the other produces a function that is right about the first index and wrong about the last, which is a genuinely unpleasant bug to find.

✅ Option B — one loop, one flag

// Option C — one loop, two named doors
const findFirst = (nums: number[], t: number) =>
  findBoundary(nums, t, true);

const findLast = (nums: number[], t: number) =>
  findBoundary(nums, t, false);

function searchRange(nums: number[], target: number) {
  return [findFirst(nums, target), findLast(nums, target)];
}

// Reads like English at the call site, and there is still
// exactly one loop to keep correct.

One loop to keep correct. The honest cost is that findBoundary(nums, target, false) is opaque at the call site — false what? The thin findFirst / findLast wrappers above cost two lines and buy back the readability, which is why this is the version shipped below.

The rule of thumb: boolean parameters are a smell when they change what a function does, and fine when they change which direction it does the same thing in. Here the loop, the invariant, and the complexity are identical either way — only the bias differs — so the flag is describing a genuine symmetry rather than hiding two unrelated functions behind one name. Wrap it in named helpers and the call site never has to know.

Final Result

The Verified Solution

One loop, two biases — record on a match, then keep shrinking toward the side you want.

Final — Attempt 4

// O(log N) time, O(1) space — two boundary searches
function findBoundary(
  nums: number[], target: number, findFirst: boolean,
): number {
  let left = 0;
  let right = nums.length - 1;
  let answer = -1;               // the not-found result

  while (right >= left) {         // inclusive bounds → >=
    const middle = Math.floor((left + right) / 2);

    if (nums[middle] > target) {
      right = middle - 1;         // too big — shrink from the end
    } else if (nums[middle] < target) {
      left = middle + 1;          // too small — shrink from the start
    } else {
      answer = middle;             // record, do NOT return
      if (findFirst) right = middle - 1;  // an earlier hit may exist
      else left = middle + 1;            // a later hit may exist
    }
  }
  return answer;
}

function searchRange(nums: number[], target: number): number[] {
  return [
    findBoundary(nums, target, true),
    findBoundary(nums, target, false),
  ];
}

// [5, 7, 7, 8, 8, 10], target 8  →  [3, 4]

Solution	Time	Space	Verified
Two boundary searches (Attempt 4) Verified ✓	O(log N)	O(1)	Empty, single-element, all-duplicates, absent-target, and both ends
Binary search for any hit, then expand outward linearly	O(N)	O(1)	Correct, but `[8,8,…,8]` makes the expansion scan the whole array — fails the required O(log n)
Linear scan for the first and last match	O(N)	O(1)	Correct and simple, but ignores the sort and violates the stated bound

Two sequential searches cost 2 × log₂(N), and constant multipliers drop out of big-O — so this is O(log N). On the maximum 10⁵-element input that is roughly 34 comparisons in total.

Reuse This

Template: Record-and-Shrink

The generic shape behind this solution — reach for it whenever the answer is the edge of a region rather than any member of it.

Pseudocode

function findBoundary(nums, target, findFirst):
    left = 0
    right = length(nums) - 1
    answer = -1                   // the not-found result

    while right >= left:          // inclusive bounds pair with >=
        middle = floor((left + right) / 2)

        if nums[middle] > target:
            right = middle - 1    // too big — shrink from the end
        else if nums[middle] < target:
            left = middle + 1     // too small — shrink from the start
        else:
            answer = middle       // record — do NOT return
            if findFirst:
                right = middle - 1   // an earlier hit may exist
            else:
                left = middle + 1    // a later hit may exist

    return answer

// Invariant: left only increases, right only decreases.
// Every branch above obeys it, so the window must close.

When to reach for this

Any time the answer is a boundary rather than a member: first/last occurrence, lower_bound / upper_bound, insertion points, or the first true of a monotonic predicate — that last one is how LC 278 and LC 875 work with no array at all.

The trap this journey hit

Moving a pointer in the direction that grows the window. Three of the six bugs above were that exact mistake wearing different clothes — an empty branch, a backwards left, and a forwards right.

Test Yourself

Quiz: Check Your Understanding

Question 1 of 9 Score: 0

A binary search over [5,7,7,8,8,10] for target 8 leaves the else branch (the nums[middle] === target case) empty. What happens? basic

Only the two mismatch branches move a pointer. On a match nothing changes, so the next iteration recomputes middle = Math.floor((3 + 5) / 2) = 4 from identical state and takes the same branch. An empty else in a binary search is not a no-op — it is an infinite loop.

Keep Learning

Bugs are part of the process 🎉

Six real bugs, six real fixes — that's what getting to a correct O(log N) boundary search actually looks like.

Next, while the record-and-shrink muscle is warm: LeetCode 35 — Search Insert Position (the same loop, reading left after it exits), then LeetCode 278 — First Bad Version and LeetCode 33 — Search in Rotated Sorted Array. The full pattern walkthrough lives on the Binary Search pattern page.

← Back to Binary Search Solve on LeetCode ↗

Find First and Last Position: 6 Bugs to a Clean Solution

LeetCode 34 — Find First and Last Position of Element in Sorted Array

Two Searches, Not One

Search biased left

Search biased right

Share one implementation

Attempt by Attempt

Record-and-Shrink, Step by Step

Why the Wrong Pointer Hangs

Key Takeaways

A while loop that doesn't shrink its window is an infinite loop

Finding a match is not finding the boundary

left only grows, right only shrinks — no exceptions

On a match, record and continue

>= vs > decides whether a one-element window is ever examined

Two answers usually mean two passes

Two Copies or One Flag?

The Verified Solution

Template: Record-and-Shrink

Quiz: Check Your Understanding

Bugs are part of the process 🎉

Find First and Last Position:
6 Bugs to a Clean Solution