01 / The idea
Where does 14:20 fit?
NOAA publishes tide predictions for its stations. For San Francisco on 13 September 2026, that is a height for every hour, 24 readings, and the four times the tide turns. Someone launching a kayak at 14:20 wants the height then, and 14:20 is not one of the readings. The first job is to find where 14:20 fits: after 14:00, before 15:00.
Reading from the top works for 24 readings. It is less charming for a year of hourly predictions, 8,760 of them, or a year at one-minute intervals, more than half a million. But the readings are sorted by time, and that changes everything. Compare 14:20 with the reading in the middle, and a single comparison tells you which half cannot hold the answer.
That is sorting’s payoff, and binary search is how you collect it. The idea is old; John Mauchly described it in the 1946 Moore School Lectures. Getting the edges right is the part people still trip over. When Jon Bentley set it as an exercise for professional programmers, ninety percent of them failed to produce a correct version.
02 / Name the rule
Keep a range where the answer can be, and halve it.
Every question in this lesson has the same shape: find the first position where a yes or no test turns yes. “Is this reading later than 14:20?” is no for 00:00 through 14:00 and yes from 15:00 on, because the readings are sorted. Binary search finds where no becomes yes.
It keeps two positions, low and high, and a promise: everything
before low is a no, and everything from high on is a yes. At the start,
low is 0 and high is the length of the list, so the promise holds trivially. Each probe tests
the middle position. A yes moves high down to it; a no moves low to just past it. When low meets
high, that position is the answer: the first yes, or the end of the list if there is none.
Two tests cover almost everything. Lower bound is the first value at least the target, where it would be inserted before any equal values. Upper bound is the first value greater than the target, where it would go after them. Between them, they bracket every copy of the target.
Why low + (high − low) / 2?A bug that waited nine years
The obvious midpoint is (low + high) / 2. In a language with fixed-size
integers, low + high can overflow when the array is large enough, even though
the midpoint itself fits. In 2006 Joshua Bloch wrote that the binary search he had put in
Java’s java.util.Arrays had exactly this bug, reported “after lying in wait
for nine years or so,” and that the version Bentley proved correct in Programming Pearls had it too.
low + (high − low) / 2 never adds two large numbers. Go’s own sort.Search computes its midpoint with a comment saying it avoids overflow. JavaScript
numbers do not overflow at array sizes, but the habit costs nothing.
03 / Follow one operation
Four probes to 14:20, five to 13:00.
The table holds the 24 hourly readings and the four turns of the tide. It answers four questions: the height at 14:20, the height at 13:00, the next turn after 14:20, and the readings from 06:00 up to 09:00.
Before you watch, predict how many readings the search looks at to place 14:20 among 24. The animation replays each recorded probe. Try it lets you ask your own questions, including times outside the day.
Halve what is left, and keep the boundary honest.
Sorted by time. Ask a question to start a search.
- 0 00:00 1441
- 1 01:00 1603
- 2 02:00 1597
- 3 03:00 1409
- 4 04:00 1090
- 5 05:00 743
- 6 06:00 479
- 7 07:00 375
- 8 08:00 444
- 9 09:00 659
- 10 10:00 966
- 11 11:00 1295
- 12 12:00 1583
- 13 13:00 1771
- 14 14:00 1796
- 15 15:00 1622
- 16 16:00 1279
- 17 17:00 857
- 18 18:00 476
- 19 19:00 237
- 20 20:00 182
- 21 21:00 296
- 22 22:00 536
- 23 23:00 836
0 probes so far
Twenty-four readings, one per hour.
San Francisco’s predicted tide for 13 September 2026, sorted by time. Sorted order is the whole trick: one comparison can rule out half of what is left.
Reduced motion: choose a scene to see its completed state.
Read this scene
San Francisco’s predicted tide for 13 September 2026, sorted by time. Sorted order is the whole trick: one comparison can rule out half of what is left.
San Francisco’s predicted tide for 13 September 2026, sorted by time. Sorted order is the whole trick: one comparison can rule out half of what is left.
Watch restarts when you return. Step through keeps your selected step. Try it keeps the same day of readings; nothing you ask changes them.
04 / Read the shape
One search, two bounds, three questions.
Basic form is partitionPoint, which finds the first position
where a test turns true, and the two bounds built on it. Nothing in it knows about tides;
any sorted list of numbers works. In the wild wraps it in TideTable. It checks once, when the table is built, that readings and turns are
in strictly increasing time. Every question after that trusts the order.
Each question is a bound in disguise. The height at a minute needs the last reading at or
before it: one upper bound, minus one. The next turn is an upper bound on the turns. A
window from from up to to is two lower bounds, so a reading
exactly at to is left out and windows can sit side by side without sharing a reading.
One half-open search, partitionPoint, finds the first index where a yes/no test turns true. Lower bound and upper bound are that search with “at least” and “greater than.” Pass an array to record every probe.
export type Probe = { low: number; high: number; mid: number; right: boolean };
// The first index in [0, length) where isRight is true, or length if there is none.
// isRight must be false for some prefix and true for everything after it; sorted data
// makes that so. Pass an array as probes to record every index the search looks at.
export function partitionPoint(
length: number,
isRight: (index: number) => boolean,
probes?: Probe[]
): number {
if (!Number.isSafeInteger(length) || length < 0)
throw new RangeError('length must be a whole number of at least 0');
let low = 0;
let high = length;
// Invariant: every index below low is left, and every index from high on is right.
// The answer is somewhere in [low, high], and the gap halves on every probe.
while (low < high) {
// Not (low + high) / 2: this form cannot overflow in languages with fixed-size integers.
const mid = low + Math.floor((high - low) / 2);
const right = isRight(mid);
probes?.push({ low, high, mid, right });
if (right) high = mid;
else low = mid + 1;
}
return low;
}
// The first index whose value is at least target: where target would go before any equal values.
export function lowerBound(sorted: readonly number[], target: number, probes?: Probe[]): number {
return partitionPoint(sorted.length, (i) => sorted[i] >= target, probes);
}
// The first index whose value is greater than target: where target would go after any equal values.
export function upperBound(sorted: readonly number[], target: number, probes?: Probe[]): number {
return partitionPoint(sorted.length, (i) => sorted[i] > target, probes);
}type Probe struct {
Low int `json:"low"`
High int `json:"high"`
Mid int `json:"mid"`
Right bool `json:"right"`
}
// PartitionPoint returns the first index in [0, length) where isRight is true, or
// length if there is none. isRight must be false for some prefix and true for
// everything after it; sorted data makes that so. A non-nil probes records every
// index the search looks at.
func PartitionPoint(length int, isRight func(index int) bool, probes *[]Probe) int {
if length < 0 {
panic("length must be a whole number of at least 0")
}
low, high := 0, length
// Invariant: every index below low is left, and every index from high on is right.
// The answer is somewhere in [low, high], and the gap halves on every probe.
for low < high {
// Not (low + high) / 2: that sum can overflow a fixed-size int.
mid := low + (high-low)/2
right := isRight(mid)
if probes != nil {
*probes = append(*probes, Probe{low, high, mid, right})
}
if right {
high = mid
} else {
low = mid + 1
}
}
return low
}
// LowerBound returns the first index whose value is at least target: where target
// would go before any equal values.
func LowerBound(sorted []int, target int, probes *[]Probe) int {
return PartitionPoint(len(sorted), func(i int) bool { return sorted[i] >= target }, probes)
}
// UpperBound returns the first index whose value is greater than target: where
// target would go after any equal values.
func UpperBound(sorted []int, target int, probes *[]Probe) int {
return PartitionPoint(len(sorted), func(i int) bool { return sorted[i] > target }, probes)
}Reading the TypeScriptA callback and an optional record
partitionPoint takes the test as a callback, so the same loop serves both
bounds and any other monotone question. probes?.push records a probe only when
the caller passed an array.
Math.floor((high - low) / 2) keeps the midpoint a whole number. Number.isSafeInteger rejects fractional lengths and minutes. The bounds are positions
in the list, so both must be whole numbers for the search to stay inside it.
Reading the GoPointers for the optional record
The probe record is a *[]Probe, nil when nobody wants it. Integer division
already rounds toward zero, so (high-low)/2 needs no floor.
HeightAt and NextTurn return a value with an ok flag instead of null, and ReadingsBetween returns an error for a window
that ends before it starts. The tests check LowerBound against the standard
library’s sort.SearchInts and slices.BinarySearch.
What would I normally use in application code?Go ships it; JavaScript does not
Go has sort.Search(n, f), which
returns “the smallest index i in [0, n) at which f(i) is true,” exactly this lesson’s partitionPoint, and slices.BinarySearch,
which returns the earliest position of a target and whether it was found.
JavaScript arrays have no binary search method. A ten-line lower bound like this lesson’s
is common, or d3-array’s bisectLeft, bisectRight, and bisector(accessor), which searches objects by a
field and offers center for the closest value. Python’s bisect module has the same left and right pair.
05 / Try a decision
Lower bound or upper bound?
The two bounds differ only on equal values, which makes swapping one for the other feel harmless. Decide where it is not before the feedback tells you.
06 / Follow the cost
Twenty probes for a year of minutes.
Here is every operation at a glance, with n readings, t turns, and k readings in a window. The rest of this section is about the first row.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Find a bound in n sorted values | O(log n) | O(1) | At most ⌈log₂(n + 1)⌉ probes. Each probe halves the positions still possible. |
| Height at a minute | O(log n) | O(1) | One upper bound, then one straight-line calculation between the two readings either side. |
| Next turn of the tide | O(log t) | O(1) | The same search over t turns instead of n readings. |
| Readings in a window | O(log n + k) | O(k) | Two lower bounds find the window in O(log n); copying its k readings costs k. |
| Build the table | O(n + t) | O(n + t) | Checks once that both lists are in time order. Checking before every search would cost O(n) each time and undo the point. |
| Sort unsorted readings first | O(n log n) | O(n) | Worth it when the list is searched many times. For one question, a scan is cheaper. |
| Insert a reading in order | O(n) | O(1) amortized | The search finds the place in O(log n), but every later reading shifts along the array. |
Each probe leaves at most half the positions that were still possible, so after p probes at most n ÷ 2p remain, and the search needs at most ⌈log₂(n + 1)⌉ probes. For the story’s 24 readings, that is 5. Placing 14:20 took 4 and 13:00 took 5.
Across every possible answer, this lesson’s model measured the average too. For the day’s 24 readings, a search averaged 4.72 probes, where a scan from the start averaged 13 comparisons. For a day at one-minute intervals, 1,440 readings, it was 10.58 against 721. For a year of hourly readings, 8,760, it was 13.13 against 4,381. And for a year at one-minute intervals, 525,600 readings, the search never needed more than 20 probes, against an average of 262,801 comparisons for the scan.
Those are counts, not timings. For 24 readings, the difference between 5 probes and 13 comparisons is too small to measure in a user interface, and a scan is fine. The gap only matters because it keeps growing: multiply the data by a thousand and the scan does a thousand times more work, while the search adds about ten probes.
The cost binary search does not show is the one paid up front. The data must already be sorted, and it must stay sorted. Sorting costs O(n log n) once. Inserting one reading in order still shifts every reading after it, which is why data that changes constantly usually lives in a tree instead.
07 / Give it a real job
Know what the numbers mean before you search them.
In a real app, the table is built from NOAA’s published predictions for the chosen station
and day, and the tide screen calls heightAt as someone drags a time slider, nextTurn for the headline, and readingsBetween to draw the part of the
curve on screen.
What the table leaves out is a decision too. Its heights between readings are straight lines, while NOAA’s curve is not, so the estimate at 14:20 is close but not NOAA’s number, and the highest reading, 1,796 mm at 14:00, is below the predicted high of 1,809 mm at 13:38. That is why the turns are a separate list rather than something worked out from the readings. And its minutes count from local midnight: on a day when clocks change, a day has 23 or 25 hours, so a real app should search on timestamps instead.
Build UIs?See the binary searches already running under your pages, and the day you write one.
Where it already is in your components
Virtualized lists render only the rows on screen, so on every scroll they must work out
which row comes first. TanStack Virtual keeps each row’s start offset in order and calls a findNearestBinarySearch over them with the scroll offset. hls.js does the same
kind of search over video segments to find the one that holds the playback position after a
seek.
Chart tooltips are the other place. d3-array’s bisector searches rows by a
date or number field, and its center method returns the index of the closest value,
which is what a hover readout snapping to the nearest point needs.
When you have to own it
You are building a log viewer, or the code panel in an internal tool. The status bar
should say “Ln 12, Col 5”, but the caret only knows it sits at character 4,817. Keep an
array of the offsets where each line starts. It is sorted for free, because offsets only
grow. The caret’s line is the last start at or before it: an upper bound, minus one. The
column is the offset minus that start. A caret exactly on a line start lands on that line,
and a caret after a trailing newline lands on the empty last line, just as your editor
shows it. React’s onSelect fires when the caret moves; in Svelte, listen for the textarea’s selectionchange.
Now the document is 200,000 lines, and a linter in a worker sends its problems back as character offsets. Rebuilding the starts means reading millions of characters on every keystroke. Update them from the edit instead. Starts before the edit stay put, starts after it move by the change in length, and the starts inside the edited range are replaced by the newlines in the inserted text. Each diagnostic then costs one search of at most 18 probes. Tag every lint result with the version of the document it read, and drop the ones an edit has overtaken: their offsets point at the wrong characters now.
A status line reading “Ln x, Col y” from the caret: line starts built once per text, then an upper bound minus one. React reads the caret in onSelect; Svelte listens for the textarea’s selectionchange.
import { useMemo, useState } from 'react';
// The first index whose value is greater than target.
function upperBound(sorted: readonly number[], target: number): number {
let low = 0;
let high = sorted.length;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] > target) high = mid;
else low = mid + 1;
}
return low;
}
// Where every line begins, as a character offset: line 1 at 0, and one more after each
// "\n". Already sorted, because offsets only grow. LF line endings only.
export function lineStarts(text: string): number[] {
const starts = [0];
for (let i = text.indexOf('\n'); i !== -1; i = text.indexOf('\n', i + 1)) starts.push(i + 1);
return starts;
}
// The line is the last start at or before the offset, so a caret sitting exactly on a
// line start belongs to that line. Lines and columns count from 1, as editors show them.
export function caretPosition(starts: readonly number[], offset: number) {
const line = upperBound(starts, offset) - 1;
return { line: line + 1, column: offset - starts[line] + 1 };
}
export function CaretStatus() {
const [text, setText] = useState('');
const [caret, setCaret] = useState(0);
// Rebuilt when the text changes, not every time the caret moves.
const starts = useMemo(() => lineStarts(text), [text]);
const { line, column } = caretPosition(starts, caret);
return (
<>
<textarea
value={text}
onChange={(event) => setText(event.target.value)}
// React fires onSelect for caret moves and edits too, not only for selected text.
onSelect={(event) => setCaret(event.currentTarget.selectionStart)}
/>
<p>
Ln {line}, Col {column}
</p>
</>
);
}
08 / Make the call
Ask whether the data is sorted, and whether it stays that way.
Reach for binary search when the data is sorted, changes rarely, and gets asked many
questions: where a value fits, the nearest value, or everything in a range. It also works on
any yes-or-no question whose answers switch from no to yes exactly once, which is how git bisect finds the first bad commit.
Look elsewhere when the question changes. Only exact matches, never ranges or nearest values: a hash map answers in O(1) on average. A short list: scan it. Keys evenly spaced, like these hourly readings: compute the position directly, since 14:20 belongs after reading 14 by division alone; binary search earns its place when the spacing is uneven, like the four turns. Frequent inserts and deletes while staying ordered: a balanced tree or an ordered map, which searches the same way but moves nothing on insert.
09 / Take the idea with you
Explain it without saying “binary search.”
“I keep two markers: everything before the first is too early, everything from the second on is late enough. I check the middle, move one marker to it, and repeat until the markers meet. Where they meet is the first thing late enough.” That describes the mechanism. The name is what you call it in a review.
Before moving on, explain three things without the name: why 14:20 needed four probes, why a
window from 06:00 up to 09:00 leaves 09:00 out, and why swapping the bounds broke only
midnight. Then find a sorted array in your own code that is searched with find, and decide whether it is big enough to care.
Connections to follow nextRelated lessons
- Sorting puts data in the order binary search depends on.
- Hash map finds exact keys faster, and cannot answer “nearest” or “between” at all.
- Binary search tree and ordered map keep data searchable this way while it changes.