Off-by-one again in your LeetCode binary search solution?

[Lomanu4]

“Although the basic idea of binary search is straightforward, the details are surprisingly tricky...

In fact, binary search has been incorrectly implemented in textbooks, published code, and production software for decades.”

— Donald Knuth, The Art of Computer Programming, Vol. 3

“I had a bug in binary search that took me days to find. It was in the JDK. The bug was in the JDK for nine years and no one noticed.”

— Joshua Bloch,

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

Binary search is a beautiful algorithm — but implementing it is full of sharp edges:

• off-by-one errors
• lo <= hi vs lo < hi
• hi = mid vs hi = mid - 1
• mid overflow
• unreadable loops

The

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

class helps to abstract away those details.

? How the API Works


You provide a lambda that tells the algorithm which direction to search.

Just return:

• -1 → search left
• 1 → search right
• 0 → stop (target found)

It follows the same logic as Comparator.


BinarySearch.forInts(Range.closed(lo, hi))
.insertionPointFor((lo, mid, hi) -> ...)
.floor(); // or .ceiling()
floor() or ceiling()?


Once the search narrows to an insertion point, you choose:

• .floor() → the last value that the lambda "search left" or stop. e.g., last i where nums <= x
  [*].ceiling() → the first value that the lambda "search right" or stop. e.g., first i where nums >= x
  

? LeetCode 875: Koko Eating Bananas


int minSpeed(List<Integer> piles, int h) {
return BinarySearch.forInts(Range.closed(1, max(piles)))
// if Koko can finish, eat slower, else eat faster
.insertionPointFor((lo, speed, hi) -> canFinish(piles, speed, h) ? -1 : 1)
// ceiling() is the first value that canFinish()
.ceiling();
}
? LeetCode 69: Integer Square Root


int mySqrt(int x) {
return BinarySearch.forInts(Range.closed(0, x))
// if square is larger, try smaller sqrt
.insertionPointFor((lo, mid, hi) -> Long.compare(x, (long) mid * mid))
// floor() is the max whose square <= x
.floor();
}
? LeetCode 410: Split Array Largest Sum


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))
// if canSplit, try smaller sum, else try larger sum
.insertionPointFor((lo, maxSum, hi) -> canSplit(nums, maxSum, k) ? -1 : 1)
// floor is the largest that can't split, ceiling is the min that can
.ceiling();
}
? TL;DR: Pattern Summary

Problem	Search Domain	Predicate	Result
Eating bananas	forInts	canFinish(speed) ? -1 : 1	.ceiling()
Square root	forInts	compare(x, mid²)	.floor()
Split array	forInts	canSplit(sum) ? -1 : 1	.ceiling()

? Can I Use This in LeetCode?


Not directly. LeetCode doesn’t support third-party libraries.

But you can use it to:

• quickly prototype and verify your binary search algorithm
  • avoid wrestling with bugs and boilerplate until you know the algorithm works.
• learning binary search intent-first

? Closing Thoughts


Mastering the thinking model of binary search is absolutely worthwhile. The ability to structure a search around monotonicity and directional reasoning is a form of higher-order abstraction that's fun and useful.

But you shouldn't have to spend your time wrestling with off-by-one bugs, loop bounds, or whether to do high = mid or low = mid + 1. Those are tedious, error prone and anything but fun (nor practically useful). They drag you down into the mud of mind-numbing, imperative twiddling.

?

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

?

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.