Binary Search: The Meguru Method

Why Traditional Binary Search Can Be Frustrating 😫

If you’ve ever implemented binary search from a textbook, you know the struggle:

• Should it be left <= right or left < right?
• Do you return -1, left, right, mid or something else?
• And why do off by one errors haunt you every time?

Python

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # Return inside the or outside loop?
        elif arr[mid] < target:
            left = mid + 1  # Add one or subtract one?
        else:
            right = mid - 1  # Can't remember tbh...

    return -1  # Return what again?

C++

int binary_search(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = static_cast<int>(arr.size()) - 1;

    while (left <= right) {
        int mid = std::midpoint(left, right);

        if (arr[mid] == target) {
            return mid; // Return inside the loop?
        } else if (arr[mid] < target) {
            left = mid + 1; // Add one here right?
        } else {
            right = mid - 1; // Can't remember tbh...
        }
    }

    return -1; // What do we return again?
}

Annoying, right? Let’s fix that.

A Better Way: Think in Terms of True and False 🕵

Binary search operates on monotonic predicates^[1]. Consider a predicate $p$ defined over a search space $S$:

$$p:S\to \{\text{True},\text{False}\}$$

When $p$ is monotonic, it partitions the space into two contiguous regions: one where the predicate evaluates to False and another where it evaluates to True. The ordering can go either way:

FalseFalseFalseTrueTrueTrue

Or similarly:

TrueTrueTrueFalseFalseFalse

Binary search can find this transition boundary. Instead of juggling left and right indices and worrying about +1/-1, an easier strategy uses two pointers that converge toward the transition boundary through successive refinement.

Once the transition boundary is identified, we can select the True or False value depending on what the problem requires.

The Meguru Implementation 🥷

The version popularized by Codeforces user Meguru does exactly this.

We initialize and maintain two pointers:

• ok: a position already confirmed valid; $p(\text{ok})=True$

• ng: a position already confirmed invalid; $p(\text{ng})=False$

At each step:

1. $\text{mid}\leftarrow \lfloor (\text{ok}+\text{ng})/2\rfloor$
2. If $p(\text{mid})$ is true, set $\text{ok}\leftarrow \text{mid}$
3. Else, set $\text{ng}\leftarrow \text{mid}$

This rapidly shrinks the interval between ok and ng. Because one pointer is always valid and the other invalid, the search never overshoots or loses track of the boundary. The loop terminates when the two pointers are adjacent (for $S\subset \mathbb{Z}$) or within some tolerance $\epsilon$ (for $S\subset \mathbb{R}$). At that point, the boundary has been found, and ok is returned.

Python

def binary_search(arr: list[int], target: int) -> int:
    ok: int = ...  # confirmed valid
    ng: int = ...  # confirmed invalid

    while abs(ok - ng) > 1:
        mid: int = (ok + ng) // 2

        if p(mid):
            ok = mid  # mid is valid
        else:
            ng = mid  # mid is invalid

    return ok

C++

int binary_search(const std::vector<int>& arr, int target) {
    int ok = ...; // confirmed valid
    int ng = ...; // confirmed invalid

    while (std::abs(ok - ng) > 1) {
        int mid = std::midpoint(ok, ng);

        if (p(mid)) {
            ok = mid; // mid is valid
        } else {
            ng = mid; // mid is invalid
        }
    }

    return ok;
}

Note that neither ok nor ng are evaluated during the loop. At each step we only test the midpoint, which always satisfies

$$min(\text{ok},\text{ng})<\text{mid}<max(\text{ok},\text{ng})$$

If the solution lies at index $k$, then throughout execution we maintain the invariant

$$\text{ok}\le k<\text{ng}\text{(when searching True to False)}$$

or equivalently

$$\text{ng}<k\le \text{ok}\text{(when searching False to True)}$$

Thus $k$ is guaranteed to lie within the half open interval between the two pointers: $[\text{ok},\text{ng})$ in the first case, or $(\text{ng},\text{ok}]$ in the second. When the loop terminates returning ok therefore yields the True position exactly at the boundary.

Remember ‼️

ok always points to a position where the predicate is True, and ng always points to where it's False. When they're adjacent, we've found the boundary.

Why This Works 🧐

The invariant $\text{ok}\le k<\text{ng}$ (or $\text{ng}<k\le \text{ok}$) is maintained throughout the search. Since one pointer is always valid and the other invalid, you never lose track of the boundary. No off by one errors, no confusion about loop conditions.

Practice Problems 🤓

Start with these LeetCode problems to get comfortable with the pattern:

1. 704. Binary Search
2. 35. Search Insert Position
3. 278. First Bad Version
4. 875. Koko Eating Bananas
5. 1011. Capacity To Ship Packages Within D Days

Once you understand this approach, you'll never struggle with binary search again.

References 📚

---

1. CP-Algorithms. (2025, August 19). Binary search. Retrieved from https://cp-algorithms.com/num_methods/binary_search.html#search-on-arbitrary-predicate ↩︎