← Bank
Code Review

Binary Search Bug

Code ReviewJunior~8m
debuggingbinary-searchoff-by-one

Prompt

This is in a small PR adding a helper to look up an item by id in a sorted array — it backs a hot lookup path in our pricing service. A teammate wrote it, tests pass on their machine, and they've asked for your review. Walk me through what you'd flag, and whether you'd approve it.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

How this round runs

Rank what you find by severity and lead with the finding that actually matters, not the nit. Tell me whether you'd approve it, and what a passing test suite does and doesn't prove here.

Model answer

This is a block, not an approve. Two correctness bugs, ranked:

1 (highest — infinite loop, hangs the request). On the arr[mid] < target branch the code does left = mid. But mid was just compared and ruled out, so it should be excluded from the next window with left = mid + 1. Leaving left at mid means when the window narrows to two adjacent elements, mid keeps resolving to the same left index, left never advances, and the loop spins forever. In a hot lookup path that is not a wrong answer — it is a hung request and a tied-up worker.

Concrete failing case: arr = [1, 2, 3, 4, 5], target = 5.

left=0, right=4 -> mid=2, arr[2]=3 (3 < 5) -> left=2
left=2, right=4 -> mid=3, arr[3]=4 (4 < 5) -> left=3
left=3, right=4 -> mid=3, arr[3]=4 (4 < 5) -> left=3   (spins forever)

2 (correctness — misses the last element). Independently of the loop bug, the condition left < right exits while one candidate index is still unchecked. The infinite loop masks this today — those targets hang before they could return anything — but once left = mid is fixed, a target at the final position of its window returns -1 (a false "not found"). The condition must be left <= right.

Root cause of both: the window-narrowing invariant is wrong. After comparing mid, the half that excludes mid must move past it, and the loop must keep running while the window is non-empty (left <= right). Fix:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

A note on the green tests: passing CI here proves very little — the existing cases evidently dodge the failing windows (the bug only bites on specific targets), so I'd want the diff to add tests for the last element, an absent value, an empty array, and a single-element array before merging.

I would not block on style — left/right/mid are fine — and I'd say so, so the author knows the block is about the hang, not preference.

Signals — what a strong answer shows
  • Led with the infinite loop (hangs a hot path) before the missed-last-element bug — correctness ranked by blast radius, not reading order
  • Gave a concrete target that triggers the spin instead of asserting it abstractly
  • Named the shared root cause: the window-narrowing invariant, not two unrelated typos
  • Called out that green CI proves little here and named the missing test cases
  • Explicit approve/block call (block) with a one-line reason
Follow-ups — where it goes next
  • Would you approve it? → No — block; one of the two bugs hangs the worker. State that before discussing the fix.
  • The tests are green — doesn't that mean it's fine? → No; the cases dodge the failing windows. Name the missing ones (last element, absent, empty, single).
  • Is `(left + right)` itself a problem? → In JS no (doubles), but in a fixed-width-int language it can overflow; `left + (right - left) / 2` is the portable form.
Study this: Algorithms