Skip to content

Binary search, including on the answer

Name the check that flips once; keep lo on a no and hi on a yes.

Predict first

Before you read: predict

A payments ledger must send eight merchant payouts (amounts in thousands), in this order, within 3 settlement days. Each day it sends the next payouts in line up to a daily limit, and a payout is never split across two days. The ledger searches for the smallest daily limit that works:

What is limit at the end?

Code for this question
const payouts = [18, 7, 25, 9, 14, 30, 6, 11];const DAYS = 3;function daysNeeded(limit) {  let days = 1;  let sent = 0;  for (const p of payouts) {    if (sent + p > limit) {      days++;      sent = 0;    }    sent += p;  }  return days;}let lo = Math.max(...payouts) - 1;let hi = payouts.reduce((a, b) => a + b, 0);while (hi - lo > 1) {  const mid = Math.floor((lo + hi) / 2);  if (daysNeeded(mid) <= DAYS) hi = mid;  else lo = mid;}export const limit = hi;
Pick one

The 30-second version

Binary search finds where a yes/no check flips. Keep lo on a no and hi on a yes, test the middle, move the end that agrees, and stop when the two are neighbours. The check can ask about positions in a sorted array or about candidate answers themselves.

Name the check that flips once; keep lo on a no and hi on a yes.

How it works

Step 1 of 12

Halving needs a check that flips once: no, no, …, then yes to the end. On a sorted array, "is it at least x?" is one.
In the kitchen
  • once a jar tastes hot, every stronger jar tastes hot too → a check that flips once (step 1)

Analogy: A hot-sauce maker's tasting panel (condiment making)

A sauce maker wants the least chilli her new recipe needs to taste hot. She makes 64 test jars of one base, with 1 to 64 grams of chilli, and lines them up mild to strong.

In the tasting kitchen In the code
once a jar tastes hot, every stronger jar tastes hot too a check that flips once (step 1)
a red label on the strongest jar known not hot, a green label on the mildest known hot lo and hi, the invariant (step 3)
the panel tastes the jar halfway between the labels, and the label that agrees moves there the middle, and moving the end that agrees (steps 4–5)
she asks only "hot yet?", and the grams themselves are what she is searching searching the answer (step 11)

In real terms: halving needs a yes/no question and two ends known to answer no and yes; everything else is bookkeeping.

Breaks down when: a tired palate can call the same jar hot once and mild the next time, while a check in code answers the same every time; and jars must be made before they are tasted, while a candidate value costs nothing until it is checked.

Contrasting case: tasting from the mildest jar up, one jar at a time, until one tastes hot: every jar below the answer costs a tasting.

Examples, run for real

4.1 ExamHall EXH-4940: the deploy that broke autosave

ExamHall's essay editor stopped autosaving somewhere in the last 200 deploys. The deploy before them was known good and the current one known bad. On-call first checked deploys newest first, one at a time (EXH-4940):

4.1 EXH-4940 200 deploys after the last good one, autosave broken from deploy 137 on · checked newest first, one deploy at a time, until one still saves

MR !5240 keeps the last good deploy in lo and the first known bad one in hi, and checks the deploy between them (steps 3–5):

export function firstBadDeploy(isBad, good, bad) {
  let lo = good;
  let hi = bad;
  while (hi - lo > 1) {
    const mid = Math.floor((lo + hi) / 2);
    if (isBad(mid)) hi = mid;
    else lo = mid;
  }
  return hi;
}
4.1 MR !5240 firstBadDeploy(isBad, 0, 200): deploy 137 · it finds the right deploy wherever autosave broke, for each of deploys 1 to 200

Every check halves the deploys still in doubt (step 2). The search needs no theory of the bug, only a check that answers the same for a deploy every time.

4.2 Payments: one flip, two loop shapes

A fee table sorted by amount, asked "is the fee at least 8?":

4.2 fees [3, 5, 5, 8, 12, 20] · fee >= 8: no no no yes yes yes · one flip, first yes at index 3
4.2 invariant form (lo = -1, hi = 6, loop while hi - lo > 1) ends with hi = 3 · half-open form (lo = 0, hi = 6, loop while lo < hi) ends with lo = 3

The answers flip once, so halving can find the flip (step 1). The invariant form and the half-open form land on the same index (steps 5–6).

Try it

Answer first, then check. Nothing is saved.

Question 1 of 8

A video player shows the subtitle cue on screen at second t: the last cue that starts at or before t. The cue start times are sorted:

What does cueAt(starts, 10) give?

Code for this question
export const starts = [0, 4, 9, 15, 22, 30];export function cueAt(starts, t) {  let lo = 0;  let hi = starts.length;  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    if (starts[mid] <= t) lo = mid;    else hi = mid;  }  return lo;}
Pick one

Question 2 of 8

A venue's usher app finds where a row starts in its seat list: 60,000 seat objects sorted by row, 500 seats to a row, rows 1 to 120. Asked for row 12, the screen opened at seat 126 of row 12:

The harness counts every seat the function reads.

Which one change opens every row at its first seat and reads at most 40 seats per call?

Code for this question
export function firstSeatOf(seats, row) {  let lo = 0;  let hi = seats.length;  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    if (seats[mid].row === row) return mid;    if (seats[mid].row < row) lo = mid + 1;    else hi = mid;  }  return lo;}
Pick one

Question 3 of 8

A ledger keeps the references of today's payments in arrival order and looks one up with a binary search written for sorted lists:

What is at?

Code for this question
const refs = [5120, 3307, 6041, 2280, 4417, 7012, 1906, 5583, 2954, 4769, 3871, 8125, 6630];function find(list, ref) {  let lo = 0;  let hi = list.length - 1;  while (lo <= hi) {    const mid = Math.floor((lo + hi) / 2);    if (list[mid] === ref) return mid;    if (list[mid] < ref) lo = mid + 1;    else hi = mid - 1;  }  return -1;}export const at = find(refs, 6630);
Pick one

Question 4 of 8

A chat app opens a room at the first message posted after the reader's last read time t, in seconds since the room opened. Several messages can share a second:

What is at?

Code for this question
export const times = [901, 905, 912, 912, 912, 930, 944, 951];export function firstUnread(times, t) {  let lo = -1;  let hi = times.length;  while (hi - lo > 1) {    const mid = Math.floor((lo + hi) / 2);    if (times[mid] > t) hi = mid;    else lo = mid;  }  return hi;}export const at = firstUnread(times, 912);
Pick one

Question 5 of 8

the interviewer says: "ExamHall keeps a sitting's final scores sorted from lowest to highest, like [41, 55, 55, 55, 62, 70]. Write scoreRange(scores, s): return [first, last], the first and last index holding score s, or [-1, -1] when nobody scored s. A sitting can have 100,000 scores, so read O(log n) of them, not every copy." You have 15 minutes and a plain editor.

Before you type: say your test list out loud.

Name at least six tests, each with its input and what it expects.

Question 6 of 8

the interviewer says: "ExamHall keeps a sitting's final scores sorted from lowest to highest, like [41, 55, 55, 55, 62, 70]. Write scoreRange(scores, s): return [first, last], the first and last index holding score s, or [-1, -1] when nobody scored s. A sitting can have 100,000 scores, so read O(log n) of them, not every copy." You have 15 minutes and a plain editor.

Now write it, in 15 minutes, from a blank file that exports scoreRange.

Question 7 of 8

A video app keeps the start seconds of the last nine downloaded segments in a ring, so the list is sorted but begins partway round. It looks for the slot of the oldest segment, the one with the smallest start:

What does oldest(starts) give?

Code for this question
export const starts = [36, 42, 49, 55, 61, 68, 4, 11, 19];export function oldest(starts) {  let lo = 0;  let hi = starts.length - 1;  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    if (starts[mid] > starts[hi]) lo = mid + 1;    else hi = mid;  }  return lo;}
Pick one

Question 8 of 8

A ticket sale lets each buyer in the queue ask for 1 to 6 tickets, and the asks come in queue order, not sorted. sold[i] is the number of tickets gone once buyer i is served. For each price tier the box office finds the first buyer it cannot serve in full:

What is first?

Code for this question
const asks = [4, 2, 6, 1, 5, 3, 6, 2, 4, 1, 5, 6, 3, 2];const sold = [];let total = 0;for (const a of asks) {  total += a;  sold.push(total);}function firstShort(seats) {  let lo = -1;  let hi = sold.length;  while (hi - lo > 1) {    const mid = Math.floor((lo + hi) / 2);    if (sold[mid] > seats) hi = mid;    else lo = mid;  }  return hi;}export const first = firstShort(18);
Pick one

Go deeper

Pro tips
  1. Write the invariant first (lo always answers no, hi always yes) and loop while hi − lo > 1; most off-by-one bugs disappear. When: before typing any binary search in an interview (steps 3–5). Verify (RAN, tips.mjs): (The curriculum row's tip, [SELF].)
    tip 1 the invariant form against a scan from the front: lists of 0 to 64 entries, every flip point: 2,145 cases, all equal, no index outside the list checked
  2. Before trusting an answer search, run the check once on each end: lo must fail and hi must pass. When: whenever the ends are a guess rather than a proof (step 12). The loop never checks its ends, so a hi that fails is returned unchanged. Verify (RAN, tips.mjs):
    tip 2 jobs [40, 10, 35, 25] in 2 days · hi guessed at 40: the check says 4 days, and the search returns 40 untouched · hi = the total, 110: the search returns 60
Source

Vendor pages change, so their claims are labelled as of 2026-10-17; every outcome this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.

  • git, git-bisect documentation (the curriculum row's second source), https://git-scm.com/docs/git-bisect (git-bisect.txt). As of 2026-10-17.
    • "This command uses a binary search algorithm to find which commit in your project’s history introduced a bug."
    • "a "bad" commit that is known to contain the bug, and a "good" commit that is known to be before the bug was introduced" (steps 3 and 12: the ends known to answer each way)
  • Tech Interview Handbook, Sorting and searching cheatsheet, https://www.techinterviewhandbook.org/algorithms/sorting-searching/ (tih-sorting-searching.txt). As of 2026-10-17.
    • "Binary search compares the target value with the middle element of the array, which informs the algorithm whether the target value lies in the left half or the right half, and this comparison proceeds on the remaining half until the target is found or the remaining half is empty." (steps 1–2)
    • Its question list: "Search in Rotated Sorted Array" and "Find Minimum in Rotated Sorted Array" (step 10).
  • Tech Interview Handbook, Array cheatsheet, https://www.techinterviewhandbook.org/algorithms/array/ (tih-array.txt). As of 2026-10-17.
    • "Is the array sorted or partially sorted? If it is, some form of binary search should be possible." (steps 1, 10)
  • MDN, Array.prototype.findIndex(), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/findIndex (mdn-array-findindex.txt). As of 2026-10-17.
    • "It calls a provided callbackFn function once for each element in an array in ascending-index order, until callbackFn returns a truthy value." (a built-in that reads from the front, as the prerequisite's step 2 says of indexOf)
  • MDN, Math.floor(), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/floor (mdn-math-floor.txt). As of 2026-10-17.
    • "The Math.floor() static method always rounds down and returns the largest integer less than or equal to a given number." (step 4: the middle of two neighbours is the lower one)

Related lessons

Checked against the tools and docs as of 2026-10-17.