Solve LeetCode Binary Search Problems Using the BinarySearch class

🧭 Write Binary Search Once and For All: Solving LeetCode with BinarySearch

Binary search is a classic algorithm—but writing it correctly is surprisingly hard:

• Off-by-one errors are common
• Edge cases are messy
• Loop termination and insertion logic are easy to get wrong

This post shows how to solve three representative LeetCode problems using the expressive and safe abstraction BinarySearch.Table. With it, you can write binary search declaratively—with no manual loop logic, and no risk of infinite loops.

---

🔍 Understanding insertionPointFor(...) and How It Works

At the core of BinarySearch.Table is this method:

insertionPointFor((lo, mid, hi) -> ...)

You're responsible for telling the search which direction to go at each probe point mid.

---

❗ Two styles of binary search

BinarySearch.Table supports two distinct binary search patterns:

---

1. Target-based search (classic)

insertionPointFor((lo, mid, hi) -> compare(target, mid));

This is the traditional form of binary search—looking for an exact match in a sorted array or list.

Use this when you're trying to locate a specific value.
Returning 0 indicates a match, < 0 means go left, and > 0 means go right.

---

2. Condition-based extremum search

insertionPointFor((lo, mid, hi) -> condition(mid) ? -1 : 1);

In this form, you're not searching for a specific value, but for the minimum or maximum value for a condition to still hold.

This works best when:

• The condition is monotonic (once true, always true—or once false, always false)
• You're trying to solve optimization problems like:
  • The smallest feasible solution
  • The largest possible value before something breaks

For example:

insertionPointFor((lo, mid, hi) -> canShipWithinDays(mid) ? -1 : 1);

This guides the search toward the smallest x where the condition holds, i.e., the minimum required capacity.

Return -1 to search left (try smaller), 1 to search right (try larger).

---

No need to return 0 in this style—you only care about direction, not equality.

---

🍌 Example 1: 875. Koko Eating Bananas

Find the minimum eating speed that allows Koko to finish all bananas within h hours.

int minSpeed(List<Integer> piles, int h) {
  return BinarySearch.forInts(Range.closed(1, max(piles)))
      .insertionPointFor((lo, speed, hi) -> canFinish(piles, speed, h) ? -1 : 1)
      .floor();
}

boolean canFinish(List<Integer> piles, int speed, int h) {
  int time = 0;
  for (int pile : piles) {
    time += (pile + speed - 1) / speed;
  }
  return time <= h;
}

We use .floor() to find the maximum speed that still works.

---

🧮 Example 2: 69. Integer Square Root

Compute floor(sqrt(x)) without using built-in functions.

int mySqrt(int x) {
  return BinarySearch.forInts(Range.closed(0, x))
      .insertionPointFor((lo, mid, hi) -> Long.compare(x, (long) mid * mid))
      .floor();
}

This returns the largest r such that r² <= x.

---

📦 Example 3: 410. Split Array Largest Sum

Split nums[] into k parts, minimizing the largest sum among parts.

int splitArray(int[] nums, int k) {
  int total = Arrays.stream(nums).sum();
  int max = Arrays.stream(nums).max().getAsInt();
  return BinarySearch.forInts(Range.closed(max, total))
      .insertionPointFor((lo, maxSum, hi) -> canSplit(nums, maxSum, k) ? -1 : 1)
      .ceiling();
}

boolean canSplit(int[] nums, int maxSum, int k) {
  int count = 1, sum = 0;
  for (int num : nums) {
    if (sum + num > maxSum) {
      count++;
      sum = 0;
    }
    sum += num;
  }
  return count <= k;
}

We use .ceiling() to find the smallest feasible maximum subarray sum.

---

📌 Type and Return Value Summary

Each BinarySearch.Table variant should match the nature of the problem:

Problem	Domain Type	Comparison Strategy	Return	Reason
Koko Eating Bananas	forInts	canFinish(speed) ? -1 : 1	.floor()	Find the largest valid speed
Integer Square Root	forInts	Long.compare(x, (long) mid * mid)	.floor()	Find the largest r such that r² ≤ x
Split Array Largest Sum	forInts	canSplit(maxSum) ? -1 : 1	.ceiling()	Find the smallest feasible max sum

Notes:

• Prefer forInts when the domain is naturally integer-bounded.
• Use Long.compare(...) only when intermediate values may overflow int.
• .floor() means “last value satisfying the condition”; .ceiling() means “first value satisfying the condition”.
• For more LeetCode binary search solutions, see LeetCodeTest.

---