Linear & Binary Search

The 10-second versionCopy Anchor Link

Linear search checks elements one by one until it hits the target — dead simple, works on anything, costs O(n). Binary search does something smarter: when the data is sorted, comparing against the middle tells you which half the target cannot be in, so you discard that half and repeat. Each comparison halves the space, so a billion sorted items take about 30 lookups instead of a billion. The fine print is the whole story: the data must be sorted, you must be able to jump straight to the middle, and the bounds arithmetic has to be exactly right — this is where a famously subtle bug has lived for decades.

Why this existedCopy Anchor Link

Searching is one of the oldest jobs we ever gave a computer: look through a table of records and pull out the one you want. If the records are in no particular order, there's nothing to do but check them one at a time. That's linear search, and for a long time it was all there was.

The insight that changed everything is almost embarrassingly small: if you know the data is sorted, you already know something about every element you haven't looked at yet. A single peek at the middle rules out half the pile. Do it again and you've ruled out three-quarters. That's a logarithmic algorithm hiding in plain sight.

• 1946 — John Mauchly, one of the designers of ENIAC, is the first to write the idea down, describing the "bisection" method for searching sorted data.
• 1962 — After years of near-misses, the first fully correct published binary search finally appears. The bug-riddled gap between 1946 and 1962 is a genuine piece of computing folklore.
• 2006 — Joshua Bloch (a Java and Google engineer) writes "Nearly All Binary Searches and Mergesorts are Broken," showing that even the "correct" mid = (low + high) / 2 overflows on large inputs — and that this bug shipped inside java.util.Arrays.binarySearch for nearly a decade.

Why it mattered then: sorting and searching were the first genuinely useful things computers did — payroll, census, inventory. Halving turned "wait overnight" into "wait a second," and that is what made the machine pay for itself.

Inside the inventor's headCopy Anchor Link

Start at the start. You've got a million sorted numbers and you want 42. Your first instinct — the obvious one — is to walk the list: check 1, check 2, check 3. On average that's half a million comparisons. Fine for ten items, hopeless for a million.

Then the pivot. You already know the list is sorted. So look at the middle. If the middle is bigger than 42, then 42 cannot possibly be anywhere to its right — the whole right half is larger, and you just deleted it from consideration in one glance.

Here's the trap that ate fifteen years of published code. You're writing the cut-the-middle step, and the "obvious" midpoint is this:

// The obvious midpoint.const midNaive = (lo, hi) => Math.floor((lo + hi) / 2);// The safe version — same answer, no overflow.const midSafe = (lo, hi) => lo + Math.floor((hi - lo) / 2);

Both compute the same number mathematically. But lo + hi can blow past the largest representable integer — in C, (lo + hi) wraps to a negative number for indices past INT_MAX / 2, and the "middle" lands nowhere near the middle. On 32-bit hardware with an array over a gigabyte, that's a real array index, and it crashes or loops forever. The fix, lo + (hi - lo) / 2, subtracts first so the intermediate value never gets large. That's the whole invention: not a new algorithm, just a subtraction in the right place.

The final approachCopy Anchor Link

Linear searchCopy Anchor Link

Walk the array; the first match wins; if you reach the end, it isn't there. The invariant is trivial: everything to the left of your cursor has been checked and isn't the target.

Binary searchCopy Anchor Link

Keep a window [lo, hi) — note the half-open bracket — that is guaranteed to contain the target if the target exists at all. Look at the middle; if it's the target, done. If the target is larger, it must be in the right half; smaller, the left half. Shrink and repeat until the window is empty.

The invariant: throughout the loop, if the target is present, its index lies in [lo, hi). Every branch preserves it — dropping the left half removes only elements that are strictly smaller than the target, and dropping the right half removes only elements strictly larger. When the window empties, the invariant says the target cannot exist.

A worked traceCopy Anchor Link

Search for 56 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0..9):

Three comparisons to find one value in ten; a million items would take about twenty.

It in codeCopy Anchor Link

// O(n): works on any order, scans until it finds the targetfunction linearSearch(a, target) {  for (let i = 0; i < a.length; i++)    if (a[i] === target) return i;  return -1;}// O(log n): requires a sorted array; half-open window [lo, hi)function binarySearch(a, target) {  let lo = 0, hi = a.length;  while (lo < hi) {    const mid = lo + ((hi - lo) >> 1);    if (a[mid] === target) return mid;    if (a[mid] < target) lo = mid + 1;    else                 hi = mid;  }  return -1;}

ComplexityCopy Anchor Link

The "random access" requirement is why this needs an array and not a linked list: to cut to the middle, you have to be able to be at the middle in one step.

Where you meet it todayCopy Anchor Link

• Databases. A B-tree index is binary search's grown-up cousin — O(log n) seeks instead of a full table scan, which is the single biggest performance lever in SQL.
• git bisect. Git binary-searches your commit history to find which commit introduced a bug. log2(100000) commits is seventeen steps, not a hundred thousand.
• Every standard library. std::lower_bound (C++), bisect (Python), and Rust's slice::binary_search all expose this exact algorithm.

// JavaScript has no built-in, so you keep one around — here a "lower bound":// the first index whose value is >= x.function lowerBound(a, x) {  let lo = 0, hi = a.length;  while (lo < hi) {    const mid = (lo + hi) >> 1;    if (a[mid] < x) lo = mid + 1;    else            hi = mid;  }  return lo;}

RecapCopy Anchor Link

• Linear search is O(n) and needs no preconditions; binary search is O(log n) but demands sorted data and O(1) random access.
• Halving only works because sortedness lets a peek at the middle discard a whole half.
• The classic bug is overflow in (lo + hi) / 2; write lo + (hi - lo) / 2.
• Prefer a half-open window [lo, hi) and step to mid + 1 / mid — it kills most off-by-one errors before they happen.

Next up: Bubble, Insertion & Selection Sort — the simple sorts that quietly make binary search possible.