Binary search: halve the range every step

When the data is sorted, one look at the middle tells you which half holds the answer. So you throw the other half away. Halving 1,000,000 items reaches one item in about 20 looks. Checking them one by one could take 1,000,000 looks.

Think of it like this: the “guess my number between 1 and 100” game. You guess 50, not 1, because “higher” or “lower” rules out half of the numbers at once.

How to spot it

Words and constraints in a problem that point to this pattern:

• “Sorted array” together with “find”, “search” or “position”
• “Return the first (or last) index where…” or “the smallest value that…”
• The prompt asks for O(log n), or n is so large, up to 10⁹, that even one pass is too slow
• “Minimum speed / capacity / days so that it's possible”: if one value works, every bigger value works too
• A sorted array that has been rotated or shifted

Watch it work

The template

// First index in [0, n) where isYes(index) is true; n if there is none.
// Requires: every "no" comes before every "yes".
function firstYes(n: number, isYes: (index: number) => boolean): number {
  let lo = 0;  // everything before lo is known "no"
  let hi = n;  // everything from hi onwards is known "yes" (n = one past the end)
  while (lo < hi) {                              // more than one candidate left
    const mid = lo + Math.floor((hi - lo) / 2);  // middle, rounded down, so mid < hi
    if (isYes(mid)) {
      hi = mid;        // mid might be the first "yes": keep it in the range
    } else {
      lo = mid + 1;    // mid is a "no": the answer is strictly to the right
    }
  }
  return lo;           // lo === hi: the first "yes", or n if there was none
}

// Example: the first bad build
const builds = ["ok", "ok", "ok", "ok", "ok", "bad", "bad", "bad"];
const firstBad = firstYes(builds.length, (i) => builds[i] === "bad"); // 5

Worked example

1. The first idea: try 0, 1, 2, … until the square gets too big, then step back one. For n = 2,000,000,000 that's about 44,700 tries. It works, but the interviewer will ask for better.

   function intSqrtSlow(n: number): number {
     let x = 0;
     while ((x + 1) * (x + 1) <= n) x++; // keep going while the next square still fits
     return x;
   }
   

2. Notice the shape. Ask “is x * x > n?” for x = 0, 1, 2, and so on. For n = 10 the answers are no, no, no, no, yes, yes, yes… All the “no”s come first. That's exactly the first-yes form, so binary search applies even though there's no array.

3. Frame it with the template: search x in 0..n for the first x where x * x > n. hi = n + 1 works as “one past the end” because (n + 1)² is always bigger than n. The answer is one less than that first “too big” value.

4. Write it with the three rules.

   function intSqrt(n: number): number {
     let lo = 0;
     let hi = n + 1;                       // a "yes" is guaranteed by here
     while (lo < hi) {
       const mid = lo + Math.floor((hi - lo) / 2);
       if (mid * mid > n) hi = mid;        // too big: the first "too big" is mid or earlier
       else lo = mid + 1;                  // fits: the first "too big" is later
     }
     return lo - 1;                        // lo is the first x with x * x > n
   }
   

5. Run n = 10: lo 0, hi 11 → mid 5, 25 > 10, hi 5 → mid 2, 4 fits, lo 3 → mid 4, 16 > 10, hi 4 → mid 3, 9 fits, lo 4 → stop. Return 4 − 1 = 3. Edge cases: n = 0 gives mid 0, 0 fits, lo 1, return 0. n = 1 returns 1. About 31 steps for the largest n.

Common mistakes

• Writing while (lo <= hi) together with hi = mid: when lo, hi and mid are equal and the check says yes, nothing changes and the loop never ends.
• Writing hi = mid - 1 in the first-yes form: when mid was the first yes, it's thrown away and you return the last no instead.
• Computing mid = (lo + hi) / 2 without Math.floor: you get 2.5, and arr[2.5] is undefined, so every comparison is wrong.
• Starting with hi = n - 1 when “after the last element” or “none” is a valid answer: the search can never return n.
• Binary searching data whose yes/no answers aren't in order, such as an unsorted array: halving can throw away the half that holds the answer. You get a wrong index with no error.

Cost

In interviews