Binary search

The core idea

Binary search needs exactly one property from the search space: at every point, you can tell which half the answer is in without checking it directly. On a sorted array that's obvious — but the same idea applies to any "monotonic" space, which is why binary search shows up far more often than "is this array sorted" questions alone would suggest.

The template that avoids off-by-one bugs

function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {              // note: <=, not <
    const mid = lo + Math.floor((hi - lo) / 2); // avoids overflow in fixed-width integer languages
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

Dry run: binarySearch([1, 3, 6, 9, 12, 15, 20], 15)

Seven elements, but only two comparisons — log₂(7) ≈ 2.8, rounded up to 3 worst-case steps. Compare that to a linear scan, which could need all 7. At n = 1,000,000, binary search needs about 20 steps; a linear scan could need a million.

Binary search on the answer, not the array

This is the pattern that separates candidates who've memorized one template from candidates who understand the idea. Whenever a problem asks for the minimum value that satisfies a condition (or maximum), and "does value X work?" gets easier to check as X changes monotonically, you can binary search over the range of possible answers instead of the input array.

// minimum "speed" to eat all bananas within h hours — classic answer-space search
function minEatingSpeed(piles, h) {
  function hoursNeeded(speed) {
    let hours = 0;
    for (const pile of piles) hours += Math.ceil(pile / speed);
    return hours;
  }

  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (hoursNeeded(mid) <= h) hi = mid;   // mid works — answer could be smaller
    else lo = mid + 1;                     // mid too slow — need bigger speed
  }
  return lo;
}

The array here isn't even sorted — what's monotonic is the relationship between speed and hours needed: faster speed always means fewer or equal hours. That monotonic relationship is the real requirement for binary search, not "is the input array sorted."

Finding a boundary (first/last occurrence)

// leftmost index where nums[i] >= target — the building block for
// "find first occurrence" and most boundary-search variants
function lowerBound(nums, target) {
  let lo = 0, hi = nums.length; // note: hi = length, not length-1, here
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Upper bound, first and last position, and counting

lowerBound returns the first index whose value is at least the target. Its twin, upperBound, returns the first index whose value is greater than the target. The two differ by one character, and together they answer most "sorted array with duplicates" questions.

// first index with nums[i] > target (nums.length if there is none)
function upperBound(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] <= target) lo = mid + 1;   // the only change from lowerBound: <= instead of <
    else hi = mid;
  }
  return lo;
}

// [first, last] position of target, or [-1, -1]
function searchRange(nums, target) {
  const first = lowerBound(nums, target);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, upperBound(nums, target) - 1];
}

function countOccurrences(nums, target) {
  return upperBound(nums, target) - lowerBound(nums, target);
}

Read them as counts. lowerBound(nums, x) is the number of elements smaller than x, and upperBound(nums, x) is the number of elements at most x. Their difference is how many equal x. The same reading gives the insertion point for a new value (lowerBound) and the number of elements in a value range [a, b] (upperBound(b) - lowerBound(a)).

Dry run: searchRange([5, 7, 7, 8, 8, 10], 8)

The answer is [3, 5 - 1] = [3, 4], and the count of 8s is 5 - 3 = 2. Two searches of O(log n) each. Notice the check first === nums.length before reading nums[first]: when every element is smaller than the target, lowerBound returns nums.length, one past the end.

Deriving the loop from an invariant

Most binary search bugs are not typos. They are a loop, two updates and a return value that do not agree about what lo and hi mean. You do not need to memorise three templates; you need to answer three questions and let the code follow.

1. What does the range [lo, hi] promise? (The answer, if there is one, lies inside it.)
2. What does each branch do to keep that promise true?
3. Why must the range get strictly smaller on every pass?

Form 1: search for an exact value, closed range. The promise is: if the target is present, it is in [lo, hi], both ends included. After looking at mid you know it is not the target, so you throw it away on both sides: lo = mid + 1 or hi = mid - 1. The range gets smaller by at least one element each pass. It is empty when lo > hi, which is why the loop test is lo <= hi: a range with lo === hi still holds one candidate that has not been examined. This is the classic template.

Form 2: find the first index where a condition becomes true. The promise changes. You are looking for the boundary between a run of false and a run of true, and the answer may be one past the end (no true at all). So hi starts at n, not n - 1, and [lo, hi] promises that the first true is somewhere in it, hi included. If the condition is false at mid, the answer is after it: lo = mid + 1. If it is true, mid might be the answer, so you must keep it: hi = mid, not mid - 1. The loop runs while lo < hi and ends with lo === hi, one candidate left, which is the answer. There is nothing left to check, so there is no separate return inside the loop.

// smallest x in [lo, hi) with ok(x) true; hi if there is none (ok is false up to a point, true from then on)
function firstTrue(lo, hi, ok) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

// largest x in [lo, hi] with ok(x) true; lo - 1 if there is none (ok is true up to a point, false from then on)
function lastTrue(lo, hi, ok) {
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);   // the UPPER middle, see below
    if (ok(mid)) lo = mid;
    else hi = mid - 1;
  }
  return ok(lo) ? lo : lo - 1;
}

With firstTrue, lowerBound is firstTrue(0, n, i => nums[i] >= target) and upperBound is firstTrue(0, n, i => nums[i] > target).

Form 3: find the last index where a condition is true. This is the mirror image, and it has a trap. When the condition is true at mid, mid might be the answer, so you keep it: lo = mid. Now the range only shrinks if mid is strictly above lo. With the usual lower middle that fails: at lo = 0, hi = 1 the lower middle is 0, lo = mid changes nothing, and the loop never ends. The fix is to round the middle up in this form, as lastTrue does, so that mid > lo whenever lo < hi.

In both boundary forms, the update that keeps mid (hi = mid or lo = mid) is paired with the middle that guarantees mid is not stuck at that end. In the exact-value form mid is always thrown away, so either middle works. Two quick tests catch most mistakes: run the loop by hand on a range of size 1 and on a range of size 2, and on an array where the answer is the first element, the last element, and "none".

See the range collapse

Step through the search and watch the range collapse. Ten candidates become one in four comparisons — and the count of comparisons is just how many times you can halve the array.

Rotated sorted arrays: minimum, search and the duplicates trap

Take a sorted array and rotate it: [0, 1, 2, 4, 5, 6, 7] becomes [4, 5, 6, 7, 0, 1, 2]. It is no longer sorted, but it is two sorted runs glued together, with one drop in the middle. That structure is enough for binary search, because one comparison still tells you which side to keep.

Finding the minimum (all values distinct). Compare nums[mid] with the last element of the range. If nums[mid] > nums[hi], mid sits in the high left run and the drop, which holds the minimum, is to its right. Otherwise nums[mid] is in the low right run, so it might itself be the minimum: keep it with hi = mid. This is the first-true form: the condition "nums[i] <= nums[last]" is false on the high run and true on the low run.

function findMin(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] > nums[hi]) lo = mid + 1;   // the drop is to the right of mid
    else hi = mid;                            // mid is on the low run: it may be the minimum
  }
  return nums[lo];
}

Why compare with nums[hi] and not with nums[lo]: when the range happens to be one sorted run, nums[mid] >= nums[lo] is true as well, and it would send you right, past the minimum. The last element is a fixed reference: everything on the high run is larger than it, and everything on the low run is no larger.

With duplicates there is one case the comparison cannot decide: nums[mid] === nums[hi]. In [2, 2, 2, 0, 2] and [2, 0, 2, 2, 2] the middle and the end are equal, and the drop is on opposite sides. The safe move is to discard the end:

function findMinWithDuplicates(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] > nums[hi]) lo = mid + 1;
    else if (nums[mid] < nums[hi]) hi = mid;
    else hi--;                                // equal: drop one copy of the end; mid still holds that value
  }
  return nums[lo];
}

hi-- loses nothing, because nums[mid] has the same value and is still inside the range, so the minimum value remains reachable. The price is the worst case: on an array that is all one value, every step removes a single element and the search takes O(n). Say so; it is the honest complexity of this version, and a common follow-up question.

Searching for a target. The trick is that after any split, at least one half is a plain sorted run. Find that half, check whether the target falls inside its endpoints, and keep or discard it accordingly.

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {                       // [lo, mid] is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                           // [mid, hi] is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

This is searchRotated([4, 5, 6, 7, 0, 1, 2], 0). The test is nums[lo] <= nums[mid] with <=, because lo and mid can be the same index and a one-element half is sorted. With duplicates the same equality trap appears: if nums[lo], nums[mid] and nums[hi] are all equal you cannot tell which half is sorted, and you can safely discard both ends (neither can be the target, since each equals nums[mid], which was just tested). That makes the worst case O(n) again.

function searchRotatedWithDuplicates(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return true;
    if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) {
      lo++;
      hi--;
    } else if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return false;
}

Peak element: binary search without a sorted array

Here the array is not sorted at all. You are told that neighbouring values are different, and that you may imagine -∞ on both sides of the array. A peak is an element larger than both neighbours. Find the index of any one peak, in O(log n).

Compare nums[mid] with nums[mid + 1]. If the right neighbour is larger, you are going uphill, and walking right can only end at a peak: either the climb stops at an element larger than its right neighbour, or it reaches the end of the array, where the imaginary -∞ makes the last element a peak. So a peak exists in [mid + 1, hi]. If the right neighbour is smaller, the same argument on the left shows a peak exists in [lo, mid], with mid itself a candidate.

function findPeakElement(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;   // uphill: a peak is to the right
    else hi = mid;                                  // downhill: mid or something left of it is a peak
  }
  return lo;
}

This is [1, 2, 1, 3, 5, 6, 4], which has two peaks (the 2 and the 6); the search happened to find one of them. It guarantees a peak, not the highest. The promise of the range is "some peak lies in [lo, hi]", and that is all binary search needs: the half to keep comes from a local comparison, not from the array being sorted. If equal neighbours are allowed, a flat stretch can hide the direction and the argument fails, so check the constraints first.

A sorted matrix as one flat array

Suppose each row of a matrix is sorted, and the first value of each row is larger than the last value of the row above. Read row by row, the matrix is one long sorted list. You do not need to build that list; you only need to convert a position in it back to a cell. For a matrix with cols columns, the flat index k lives at row Math.floor(k / cols) and column k % cols.

function searchMatrix(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
  const rows = matrix.length, cols = matrix[0].length;
  let lo = 0, hi = rows * cols - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];
    if (value === target) return true;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

On [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] and target 3, the middles are flat positions 5 (the 11), 2 (the 5), 0 (the 1), then 1 (the 3), found. The cost is O(log(rows × cols)), which equals O(log rows + log cols). Use Math.floor for the row: without it mid / cols is a fraction in JavaScript, and indexing with a fraction gives undefined.

The flattening works only because the whole matrix is one sorted sequence. In the other well-known matrix, each row and each column is sorted but rows are not ordered against each other, the row-by-row order is not sorted, and the trick is wrong. There you start at the top-right corner and walk: a value larger than the target means the whole column below it is too large, so move left; a value smaller means the rest of the row is too small, so move down. That is O(rows + cols), and it is not a binary search. It lives with the other grid techniques in matrix problems.

function searchMatrixII(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
  let r = 0, c = matrix[0].length - 1;
  while (r < matrix.length && c >= 0) {
    const value = matrix[r][c];
    if (value === target) return true;
    if (value > target) c--;
    else r++;
  }
  return false;
}

The feasible(x) template: minimize the maximum

The bananas example earlier searched for the smallest speed that works. The same shape covers a large family of problems whose answer reads "the smallest X such that it is possible to…", or "minimize the largest …". Write the question in two parts and keep them apart:

• A check, feasible(x): given a candidate answer, a plain O(n) loop (usually greedy) says yes or no.
• A search over the range of possible answers, using firstTrue, valid because feasible is monotone: once a candidate works, every larger one works too.

Capacity to ship packages within D days. Packages must go in order; each day the ship carries consecutive packages up to its capacity. What is the smallest capacity that gets everything shipped in D days? The check is greedy: load packages until the next would overflow, then start a new day, and count the days. A bigger ship never needs more days, so the check is monotone. The smallest sensible capacity is the heaviest single package (anything less can never carry it), and the largest needed is the total weight (one day).

function shipWithinDays(weights, days) {
  const daysNeeded = (capacity) => {
    let used = 1, load = 0;
    for (const w of weights) {
      if (load + w > capacity) {
        used++;
        load = 0;
      }
      load += w;
    }
    return used;
  };

  let lo = Math.max(...weights);
  let hi = weights.reduce((sum, w) => sum + w, 0);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (daysNeeded(mid) <= days) hi = mid;      // mid works: try smaller
    else lo = mid + 1;                          // mid is too small
  }
  return lo;
}

The weights are [1, 2, …, 10] and D = 5, giving capacity 15. Each check is O(n) and the search needs about log₂(sum − max) rounds, so the time is O(n log(sum)) and the space is O(1).

Split array largest sum is the same problem in different clothes: cut an array into k consecutive pieces so that the largest piece sum is as small as possible. "Pieces needed for a given limit" replaces "days needed for a given capacity", and it is the same greedy loop. (Assume k is at most the array length; using fewer pieces than k is fine, because a piece can always be split further without raising the maximum.)

function splitArray(nums, k) {
  const piecesNeeded = (limit) => {
    let pieces = 1, sum = 0;
    for (const x of nums) {
      if (sum + x > limit) {
        pieces++;
        sum = 0;
      }
      sum += x;
    }
    return pieces;
  };

  let lo = Math.max(...nums);
  let hi = nums.reduce((total, x) => total + x, 0);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (piecesNeeded(mid) <= k) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Maximize the minimum flips the direction. Place m balls in baskets at the given positions so that the smallest gap between any two balls is as large as possible. A bigger required gap is harder, so canPlace(gap) goes from true to false, and you want the last true: the mirror form with the upper middle.

function maxMinGap(positions, m) {
  const p = positions.slice().sort((a, b) => a - b);
  const canPlace = (gap) => {
    let placed = 1, last = p[0];
    for (let i = 1; i < p.length; i++) {
      if (p[i] - last >= gap) {
        placed++;
        last = p[i];
      }
    }
    return placed >= m;
  };

  let lo = 1, hi = p[p.length - 1] - p[0];
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);   // upper middle: lo = mid must make progress
    if (canPlace(mid)) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

This assumes distinct integer positions and 2 <= m <= n; with those, a gap of 1 is always possible, so lo = 1 is a safe start. For positions [1, 2, 3, 4, 7] and m = 3 the gaps tried are 4 (no), 2 (yes), 3 (yes), giving 3 (balls at 1, 4 and 7). How to recognise the family: the answer is a number, a check on one candidate is easy, and the words "minimum possible largest", "maximum possible smallest" or "at least … at most" appear.

Real-valued search and square roots

Binary search also works when the answer is not an integer. The integer square root, the largest r with r * r <= x, is the "last true" form:

function integerSqrt(x) {
  let lo = 0, hi = x;
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);
    if (mid * mid <= x) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

For x = 40 the middles are 20, 10, 5, 7 and 6, ending at 6 (6 × 6 = 36, 7 × 7 = 49). In JavaScript mid * mid is exact up to 2⁵³, and beyond that it is rounded, yet still larger than any x below 2⁵³, so the comparison stays right. In a language with fixed-width integers the same product can overflow, which is why you will see the comparison written mid <= x / mid or with a wider type.

For a real-valued root, shrink the interval instead of looking for a boundary index, and decide how to stop. A tolerance loop such as while (hi - lo > 1e-9) looks natural and can hang: for large values, adjacent doubles are further apart than 1e-9 (near 1e15 the gap is 0.125), so the width can never get below the tolerance. A fixed number of halvings always ends.

function sqrtReal(x) {                       // x >= 0
  let lo = 0, hi = Math.max(1, x);           // the root of x < 1 is larger than x
  for (let i = 0; i < 100; i++) {
    const mid = (lo + hi) / 2;
    if (mid * mid <= x) lo = mid;
    else hi = mid;
  }
  return lo;
}

100 halvings shrink the starting width by a factor of 2¹⁰⁰, far below what a double can resolve for any x up to about 10²⁸, so the loop settles on the closest representable values. For a much larger x the starting width is too big for 100 halvings, and you would use more. sqrtReal(2) gives 1.414213562373095, and the answer is correct to about the last digit; do not compare real-valued results with ===, compare within a tolerance.

Find the duplicate by searching the value range

An array of n + 1 integers holds values from 1 to n, so by pigeonhole at least one value repeats. Find a repeated value without modifying the array and with O(1) extra space. Sorting would change it; a Set would use O(n) space. The array is not sorted, but the values are a range, and a count tells you which half of the range holds a duplicate.

Pick mid in the value range and count how many elements are at most mid. If the count is greater than mid, the values 1 … mid are too crowded: there are only mid distinct values to go round, so a duplicate lies in [1, mid]. If the count is at most mid, then more than n - mid elements are above mid, and only n - mid distinct values live there, so a duplicate lies in [mid + 1, n].

function findDuplicate(nums) {
  let lo = 1, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    let count = 0;
    for (const x of nums) if (x <= mid) count++;
    if (count > mid) hi = mid;            // too many values in [1, mid]: a duplicate is there
    else lo = mid + 1;
  }
  return lo;
}

This is [1, 3, 4, 2, 2]. Each round scans the array, and there are about log₂ n rounds, so the time is O(n log n) with O(1) space. There is also an O(n) route: treat the array as a linked list in which index i points to nums[i]. The repeated value is where two indices point at the same node, which is the entrance of a cycle, found with the fast and slow pointers from two pointers.

function findDuplicateFloyd(nums) {
  let slow = nums[0], fast = nums[nums[0]];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }
  slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Median of two sorted arrays: search the partition

Given two sorted arrays, find the median of all their elements together in O(log(min(m, n))). Merging them is O(m + n). The faster way uses the idea that the median is a cut: a split of the combined elements into a left part and a right part of the right size, where everything on the left is no larger than everything on the right.

Cut the shorter array A at position i, so A[0..i) goes left, and cut the longer array B at j = half - i, where half = floor((m + n + 1) / 2) is the size the left part should have. Choosing i fixes j, so the search is over one number. The cut is correct when the largest element on each side of the left part does not exceed the smallest on the right part. Because each array is already sorted internally, only two cross-checks are needed: A[i-1] <= B[j] and B[j-1] <= A[i].

• If A[i-1] > B[j], you took too much from A: move i left.
• If B[j-1] > A[i], you took too little from A: move i right.
• Otherwise the cut is valid. The median is the larger of the two left maxima when m + n is odd, or the average of that and the smaller of the two right minima when it is even.

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length + nums2.length === 0) throw new RangeError("the median of no values is undefined");
  let A = nums1, B = nums2;
  if (A.length > B.length) [A, B] = [B, A];     // search the shorter array
  const m = A.length, n = B.length;
  const half = Math.floor((m + n + 1) / 2);

  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = lo + Math.floor((hi - lo) / 2);
    const j = half - i;
    const aLeft = i > 0 ? A[i - 1] : -Infinity;
    const aRight = i < m ? A[i] : Infinity;
    const bLeft = j > 0 ? B[j - 1] : -Infinity;
    const bRight = j < n ? B[j] : Infinity;

    if (aLeft > bRight) hi = i - 1;
    else if (bLeft > aRight) lo = i + 1;
    else {
      const leftMax = Math.max(aLeft, bLeft);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(aRight, bRight)) / 2;
    }
  }
  throw new Error("the arrays are not sorted");
}

This is A = [1, 3, 8, 9, 15] and B = [7, 11, 18, 19, 21, 25]: eleven elements, half = 6. The left part is {1, 3, 8, 9} and {7, 11}, its largest value is 11, and since the total is odd the median is 11. The sentinels ±Infinity handle cuts at the very start or end of either array, so there are no special cases. Searching the shorter array is not only about speed: with m <= n, j = half - i always lands in [0, n]. If you search the longer one, j can go negative.

Which template for which question

Pitfalls that cost offers

• A loop that never ends. lo = mid with the lower middle hangs at a range of two. Pair lo = mid with the upper middle, or use lo = mid + 1.
• Mixing forms. hi = nums.length - 1 with hi = mid and lo < hi skips the case where the answer is one past the end; hi = nums.length with lo <= hi reads nums[nums.length]. Write the promise of [lo, hi] first.
• Reading past the end. Check first === nums.length before using nums[first] after a lower bound.
• Searching something that is not monotone. Say, in one sentence, what is true on the left of the answer and what is false on the right. If you cannot, a different technique is needed.
• Wrong bounds for the answer search. The smallest feasible value and the largest possible value must both be inside [lo, hi].
• Duplicates in rotated arrays. The comparison with the end can be a tie; plan for the O(n) worst case instead of pretending it is O(log n).
• Floating-point loops with a fixed tolerance. Use a fixed number of iterations, and compare results within a tolerance.
• Overflow in other languages. (lo + hi) / 2 and mid * mid both can; use lo + (hi - lo) / 2 and a wider type.

Recognizing it in an unseen problem

• Data is sorted, or the answer space is monotonic ("if X works, does X+1 also work?")
• The prompt says "minimum/maximum value such that…"
• A brute force would try every candidate linearly — O(n) or O(n·check)
• You can write a fast "does this candidate work?" check — that check becomes the comparison inside the binary search
• The prompt wants a boundary: the first or last position, an insertion point, "the first bad", or a count of elements below a value
• An array was rotated, or has a single peak, or has one local structure that tells you which side to keep even though it is not sorted
• "Minimize the largest" or "maximize the smallest" over a split, a capacity or a distance, with a greedy check for one candidate
• A real-valued answer, a square root, or "the k-th / median of two sorted arrays" in logarithmic time