Two Faces of Binary Search: A Tale of `lo <= hi` and `lo < hi`

Published 2026-06-20 · Markdown source

Introduction

Binary search is often taught as a single algorithm: cut the range in half, throw away the wrong side, repeat. Yet anyone who has solved more than a handful of binary-search problems knows a quiet frustration — sometimes the loop is written while (lo <= hi), sometimes while (lo < hi), and swapping one for the other turns correct code into an infinite loop or an off-by-one bug. LeetCode 704. Binary Search and 875. Koko Eating Bananas are the perfect pair to dissolve this confusion, because they are both binary searches and yet they belong to two genuinely different species. Understanding why each demands its own loop condition is understanding binary search itself.

Two Different Questions

The first thing to notice is that the two problems ask fundamentally different questions, even though both "search."

704 asks an existence question: Is this exact target present in a sorted array, and if so, where? The answer is a specific element that either exists or doesn't. There is a precise moment of success — nums[mid] == target — and a precise moment of failure — the range becomes empty.

875 asks a boundary question: What is the smallest eating speed k such that Koko finishes in time? There is no single magic element to match. Instead, there is a tipping point in a sequence of yes/no answers:

speed k:    1   2   3   4   5   6   7
finishes?:  F   F   F   T   T   T   T
                        ^
                        the answer is the first T

The answer is defined not by equality but by being the frontier between "too slow" and "fast enough." We are not looking for a value; we are looking for where one property turns into another.

This difference in the question is the root of everything that follows. The loop condition is not a stylistic preference — it is dictated by what kind of answer you are converging toward.

The 704 Template: Excluding the Probe, Needing <=

In 704, every comparison gives us strictly more than a direction; it can give us the answer itself:

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;     // success, here and now
    if (nums[mid] < target)  lo = mid + 1;   // mid is too small — discard it
    else                     hi = mid - 1;   // mid is too big — discard it
}
return -1;                                   // range emptied: not present

The defining trait of this template is that mid is excluded from both branches. When we move lo = mid + 1 or hi = mid - 1, we are asserting "I have personally examined mid, it is not the answer, throw it away." Because we just checked it with the equality test, this is safe.

Now consider what the search range means here: [lo, hi] is a closed interval of still-unexamined candidates. The loop must keep running as long as that interval contains at least one element — and a single-element interval has lo == hi. If we stopped at lo == hi, we would walk away from one untested candidate, which might be exactly the target sitting alone at the end. Therefore the condition must be lo <= hi: keep going while even one candidate remains.

Termination is never in doubt. Because both branches skip past mid, the interval shrinks on every iteration without exception. Eventually lo exceeds hi, the interval is empty, every candidate has been examined and rejected, and we return -1. The <= and the mid ± 1 updates are two halves of one coherent contract.

The 875 Template: Keeping the Probe, Needing <

Koko's search looks deceptively similar but obeys a different contract:

int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (canFinish(mid)) hi = mid;        // mid works — but keep it as a candidate
    else                lo = mid + 1;    // mid too slow — discard it
}
return lo;

Here the invariant is not "candidates not yet examined" but something stronger and more elegant:

The answer always lies within [lo, hi].

We never test for equality, because there is nothing to equal. Instead, each probe sorts mid into one of two roles. If canFinish(mid) is true, mid is a working speed — but possibly not the smallest working speed, so we dare not discard it; we write hi = mid, keeping mid inside the live range as the best candidate so far. If canFinish(mid) is false, mid is genuinely useless and everything below it is too, so lo = mid + 1 discards a whole swath.

This asymmetry — one branch keeps mid, the other excludes it — is the entire reason the loop condition changes. Because hi = mid does not move past mid, the range does not always shrink. And that creates a danger the 704 template never faces.

The Infinite Loop That Forces the <

Imagine we stubbornly used while (lo <= hi) with Koko's updates. Picture the range collapsed to a single value, lo == hi == 4:

mid = 4 + (4 - 4) / 2 = 4
canFinish(4) is true  →  hi = mid = 4     // hi does not change

Now lo == hi == 4 once more. The condition lo <= hi is still true. We compute the same mid, take the same branch, assign hi = 4 again — and again, and again, forever. The range refuses to shrink because hi = mid cannot push hi below mid when mid already equals hi. The <= condition, perfectly safe in 704, here becomes a trap.

The cure is while (lo < hi). This condition declares that the search is finished the instant lo == hi. And that is not a hack to dodge the infinite loop — it is the honest truth of the invariant. We said the answer always lives in [lo, hi]. When that interval shrinks to one value, the answer is that value. There is nothing left to decide. Stopping at lo == hi is not abandoning an unexamined candidate (as it would be in 704); it is recognizing that the two walls have met on the answer.

Why You Return lo, and Never mid

The two templates also differ in how they deliver their answer, and this is a tell of their deeper nature.

704 returns mid the moment it finds equality, mid-loop. The answer is a probe that lands on its target. If the loop ever exits, the search has failed, and we return the sentinel -1.

875 never returns from inside the loop at all. When lo < hi becomes false, lo and hi have converged to the same number, and that — the meeting point of the closing walls — is the answer. We return lo (equivalently hi; they are equal). We never return mid, both because it is out of scope after the loop and because the last mid computed is merely the last place we probed, not necessarily the boundary we sought. In a boundary search, the answer emerges from convergence, not from a lucky probe.

The Unifying Principle

It is tempting to memorize "704 uses <=, 875 uses <" and move on. But the durable lesson is the rule beneath them:

The loop condition must match how the bounds move.

When mid is always discarded, the interval is a set of unexamined candidates that must be emptied to the last one — hence <=. When one side retains mid, the interval is a guarantee that brackets the answer and collapses onto it — hence <. Choose the update rule first, by asking whether your problem is exact-match (704) or find-the-boundary (875); the loop condition then follows of necessity, not of taste.

Conclusion

704 and 875 look like the same tool used twice, and in a sense they are — both halve a search space using a single comparison. But 704 hunts a specific element and must inspect every last candidate, so it excludes its probe and loops while lo <= hi. 875 hunts the frontier of a monotone property and brackets it ever tighter, so it keeps its probe on one side and loops while lo < hi, stopping the moment the brackets touch. The two conditions are not arbitrary dialects; each is the only condition that makes its update rule terminate correctly. Master that dependency, and binary search stops being a collection of fragile templates to memorize and becomes a single idea you can re-derive every time: decide what your bounds mean, move them to preserve that meaning, and let the loop condition follow.

---

Appendix: The Problems and Their Solutions

704. Binary Search

• Difficulty: Easy
• URL: https://leetcode.com/problems/binary-search/
• Topics: Array, Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

Solution (C++):

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // binary search
        int left = 0, right = nums.size() - 1;

        while (left <= right) {                  // closed interval of candidates
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) return mid; // exact match: answer found

            if (nums[mid] < target) {
                left = mid + 1;                  // mid excluded
            } else {
                right = mid - 1;                 // mid excluded
            }
        }

        return -1;                               // range emptied: not present
    }
};

875. Koko Eating Bananas

• Difficulty: Medium
• URL: https://leetcode.com/problems/koko-eating-bananas/
• Topics: Array, Binary Search

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

Solution (C++):

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1, hi = *max_element(piles.begin(), piles.end());

        while (lo < hi) {                        // bracket that contains the answer
            int mid = lo + (hi - lo) / 2;

            // hours needed at speed = mid
            long long hours = 0;
            for (int p : piles) {
                hours += (p + mid - 1) / mid;    // ceil(p / mid)
            }

            if (hours <= h) {
                hi = mid;                        // mid works — keep it as a candidate
            } else {
                lo = mid + 1;                    // too slow — discard it
            }
        }

        return lo;                               // lo == hi == minimum valid speed
    }
};