DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 8 of 16 · ~3 min

Binary Search

Kept as a flat array sorted by course code for reporting, the catalog needs a fast lookup:

function findCourseByCode(sortedCatalog, code) {
  let lo = 0, hi = sortedCatalog.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);   // written this way to avoid overflow elsewhere
    if (sortedCatalog[mid].code === code) return sortedCatalog[mid];
    if (sortedCatalog[mid].code < code) lo = mid + 1;   // target's further right — drop the left half
    else hi = mid - 1;                                   // target's further left — drop the right half
  }
  return null;
}

Halving the remaining space every comparison is the source of O(log n) — 42,000 items take about sixteen halvings to whittle down to one. Bugs here are almost never about the logic; they're off-by-one slips in lo <= hi vs. lo < hi, or mid ± 1 vs. bare mid. Write hi = mid on the "too big" branch without ever nudging toward hi = mid - 1 and you've built an infinite loop that keeps re-checking the same midpoint. If a binary search seems to hang forever, shrink the input down to two elements and step through it by hand — the missing -1 or +1 almost always surfaces right there.

Binary search on the answer, not on an array

A different-looking version of the same tool searches a range of possible answers instead of an array. Pick a candidate, write a feasibility check that flips exactly once as the candidate changes, and binary-search for the flip point directly.

Recognize it by: phrasing like "minimize the largest," or "smallest value for which this holds," where checking every possible answer one by one would eventually work but is slow, and checking a single candidate is cheap.

A degree's required courses come in a fixed order — prerequisites forbid reshuffling — but the registrar can still choose where semester boundaries fall. Given required-course credit loads in order and a fixed number of semesters, what's the lightest the heaviest semester can possibly be made?

function fitsInKSemesters(creditLoads, maxPerSemester, numSemesters) {
  let semesters = 1, currentLoad = 0;
  for (const credits of creditLoads) {
    if (currentLoad + credits > maxPerSemester) {   // this course needs a fresh semester
      semesters++;
      currentLoad = 0;
    }
    currentLoad += credits;
  }
  return semesters <= numSemesters;
}

function minimizeHeaviestSemester(creditLoads, numSemesters) {
  let lo = Math.max(...creditLoads);                         // one enormous course alone sets the floor
  let hi = creditLoads.reduce((a, b) => a + b, 0);            // everything crammed into one sets the ceiling

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);   // candidate cap on credits per semester
    if (fitsInKSemesters(creditLoads, mid, numSemesters)) {
      hi = mid;                     // this cap works — see if a tighter one still does
    } else {
      lo = mid + 1;                 // too tight to fit the required number of semesters
    }
  }
  return lo;
}

The obvious first move is to try every possible cap starting from lo and stop at the first one that works — and that costs O(n · range), with range potentially as large as the degree's entire credit total. But look at what's actually being narrowed down here: not a position in an array, a number. fitsInKSemesters is standing in for the equality test from ordinary binary search, just answering yes-or-no instead of found-or-not-found. Pick one candidate cap and step through fitsInKSemesters by hand — tally credits, and the moment adding the next course would breach the cap, seal off the current semester and start counting a new one — and something falls out of that trace: pushing the cap higher can never force more semesters, only the same number or fewer. That one-directional relationship between the candidate and the outcome is what licenses binary search at all, and spotting it is what shrinks an O(n · range) brute force down to O(n · log(range)).

Binary Search on Code Lab has the practice set.