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

Binary Search

The textbook form of binary search operates on a sorted array, halving the remaining search space every comparison:

function binarySearch(sortedArr, target) {
  let lo = 0, hi = sortedArr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);   // avoids overflow in fixed-width-int languages
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) lo = mid + 1;    // target is to the right — discard the left half
    else hi = mid - 1;                             // target is to the left — discard the right half
  }
  return -1;
}

Halving the search space every step is what makes this O(log n): the number of times you can halve n before reaching 1 is log₂ n. The bugs in binary search are almost always off-by-one errors, not logic errors — lo <= hi versus lo < hi, mid + 1/mid - 1 versus mid itself. Writing hi = mid without ever making progress toward hi = mid - 1 on the "too big" branch is exactly how you write an infinite loop that re-checks the same midpoint forever; walk through a 2-element array by hand if a binary search you've written seems to hang, since that's usually where the off-by-one shows up first.

Binary search on the answer

The less obvious form of this pattern doesn't search an array at all — it searches over a range of possible answers. Pick a candidate answer, write a canAchieve(candidate) feasibility check that's monotonic (true for every value up to some threshold, then false from there on — or vice versa), and binary search for that threshold directly.

The signal: phrasing like "minimize the maximum," "maximum value such that a condition holds," where a brute-force solution would try every possible answer one at a time, but the feasibility check for any single candidate answer is cheap and monotonic in that candidate.

function canSplit(nums, maxSum, k) {
  let subarrays = 1, currentSum = 0;
  for (const n of nums) {
    if (currentSum + n > maxSum) {     // this element has to start a new subarray
      subarrays++;
      currentSum = 0;
    }
    currentSum += n;
  }
  return subarrays <= k;               // did it fit within k subarrays at this cap?
}

function minimizeLargestSubarraySum(nums, k) {
  let lo = Math.max(...nums);                       // smallest feasible cap: one huge element alone
  let hi = nums.reduce((a, b) => a + b, 0);          // largest possible cap: everything in one subarray

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);      // candidate "max sum allowed per subarray"
    if (canSplit(nums, mid, k)) {
      hi = mid;                        // mid works — try to do even better
    } else {
      lo = mid + 1;                    // mid is too small to fit into k subarrays
    }
  }
  return lo;
}

The value being searched here isn't an index into an array at all — it's a candidate number in a numeric range, and canSplit plays the exact role that sortedArr[mid] === target played in ordinary binary search, just phrased as a yes/no feasibility question instead of an equality check. Recognizing that a brute-force "try every possible answer" loop can become this pattern — whenever the feasibility function is monotonic in the candidate answer — turns an O(n · range) brute force into O(n · log(range)).

Practice this on Code Lab: Binary Search