Overflow-Safe Midpoint Calculation for Signed Integers

Welcome back. In the previous lesson, you derived last-true search by locating the first false position, maintaining a half-open interval, and returning one position before the final boundary.

That reasoning assumes every loop iteration can safely compute a midpoint. Today we tighten that low-level detail: how to compute mid without signed-integer overflow, while preserving the rounding behavior and progress guarantees your binary-search invariant needs. This matters both for ordinary index searches and for later answer-domain searches whose bounds may be large or negative.

---

The mathematically correct formula can be unsafe code

On paper, the midpoint of two bounds is:

$$\frac{\text{lo}+\text{hi}}{2}$$

The direct implementation is familiar:

int mid = (lo + hi) / 2;

The problem is that C++ evaluates lo + hi before dividing by two. If the sum lies outside the range of int, signed overflow occurs. In C++, signed overflow is undefined behavior: the program is not merely guaranteed to “wrap around”; the compiler may make assumptions that invalidate your intended logic.

For example, on a typical 32-bit int system:

int lo = 1'800'000'000;
int hi = 2'000'000'000;

The mathematical midpoint is $1,900,000,000$, which fits in int. But the intermediate sum is $3,800,000,000$, which does not fit.

This explains why binary-search code can appear perfect under normal tests and still fail near the top of a large domain: only after several iterations may both bounds become large enough for their sum to overflow.

---

The standard binary-search repair

For the nonnegative index ranges used in the first-true and last-true templates, write:

int mid = lo + (hi - lo) / 2;

This says: start at lo, measure the width of the remaining interval, and move halfway across it.

For an ordinary half-open index interval, the contract is:

$$0\le \text{lo}\le \text{hi}\le \text{INT\_MAX}$$

Under that contract, the calculation is safe:

1. hi - lo is nonnegative.
2. Since lo is nonnegative, hi - lo cannot exceed hi, so it fits in int.
3. (hi - lo) / 2 is no greater than hi - lo.
4. Therefore,

$$\text{lo}+\frac{\text{hi}-\text{lo}}{2}\le \text{hi}$$

So the final addition also fits.

The formula also gives the lower midpoint. When lo < hi:

$$\text{lo}\le \text{mid}<\text{hi}$$

That strict inequality on the right is useful. In the half-open first-true loop, it guarantees that either hi = mid or lo = mid + 1 shrinks the interval.

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;

    if (P(mid)) {
        hi = mid;
    } else {
        lo = mid + 1;
    }
}

For the nonnegative array-index domains used so far, this is a correct and conventional choice.

---

The important caveat: signed bounds can span the entire type

The formula

lo + (hi - lo) / 2

is safer than (lo + hi) / 2, but it is not universally safe for arbitrary signed endpoints.

Consider:

int lo = std::numeric_limits<int>::min();
int hi = std::numeric_limits<int>::max();

Here hi - lo is mathematically:

$$4,294,967,295$$

That value cannot fit in a 32-bit signed int. Thus, the subtraction overflows before division.

This distinction is worth memorizing:

Bounds you have proved	Suitable midpoint expression
Ordinary nonnegative indices	lo + (hi - lo) / 2
Arbitrary signed bounds, including negative-to-positive ranges	std::midpoint(lo, hi) in C++20
Older competitive-programming environment with a known wider integer type	Compute in that wider type

The first formula is contract-safe, not magic. It is safe because ordinary binary-search indices have a restricted range. Do not silently transfer that proof to a search over every possible int.

---

Use std::midpoint for general signed integer bounds

C++20 provides the standard-library solution:

#include <numeric>

int mid = std::midpoint(lo, hi);

std::midpoint computes half the sum without overflow. It is the clearest default when your endpoints are signed integers that may be anywhere in their type’s range.

Rounding direction is part of the contract

For integral arguments, std::midpoint(a, b) rounds toward its first argument when the exact average is halfway between two integers.

Therefore, when you call it in the ordinary order:

int mid = std::midpoint(lo, hi);

with lo <= hi, it selects the lower of the two possible middle integers.

lo	hi	Exact average	std::midpoint(lo, hi)
4	5	$4.5$	4
-5	-4	$-4.5$	-5
INT_MIN	INT_MAX	$-0.5$	-1

That behavior matches:

lo + (hi - lo) / 2

whenever the latter is safe and lo <= hi.

Calling the arguments in the reverse order can select the upper midpoint instead:

std::midpoint(5, 4);  // 5

That is not wrong, but midpoint rounding must agree with the loop update rules. Your current half-open templates expect the lower midpoint.

---

Drop-in use in the boundary template

Here is the earlier first-true template written for an arbitrary representable half-open signed interval $[\text{lo},\text{hi})$:

#include <numeric>

template <class Pred>
int first_true(int lo, int hi, Pred P) {
    // Searches the representable integer interval [lo, hi).
    while (lo < hi) {
        int mid = std::midpoint(lo, hi);

        if (P(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}

The midpoint line changes; the invariant does not.

When lo < hi, the lower midpoint satisfies mid < hi. Consequently:

• In the true branch, hi = mid makes the upper bound smaller.
• In the false branch, mid + 1 is at most hi, so the increment is safe and lo advances.

This is a useful separation of concerns:

• The boundary contract says what the bounds mean.
• The invariant says what has been proved outside the active interval.
• The midpoint rule supplies a valid interior test point without arithmetic overflow.

One limitation remains: no midpoint function can make an unrepresentable endpoint exist. For example, the conceptual half-open interval containing every int would need an upper endpoint one greater than INT_MAX, which cannot be stored in an int. In that situation, choose an inclusive interval design or store the bounds in a wider type.

---

Pre-C++20 options

If C++20 is unavailable, do not reach automatically for a hand-written bit trick. Prefer widening the arithmetic, but only when you know the wider type can represent the full difference.

For conventional 32-bit signed bounds:

#include <cstdint>

std::int32_t midpoint32(std::int32_t lo, std::int32_t hi) {
    std::int64_t L = lo;
    std::int64_t H = hi;

    return static_cast<std::int32_t>(L + (H - L) / 2);
}

The conversion to int64_t happens before subtraction, so even the full distance from INT_MIN to INT_MAX is representable.

For long long bounds in typical GNU C++ competitive-programming environments, __int128_t is a common extension:

long long midpoint64(long long lo, long long hi) {
    using Wide = __int128_t;

    return static_cast<long long>(
        static_cast<Wide>(lo) +
        (static_cast<Wide>(hi) - static_cast<Wide>(lo)) / 2
    );
}

This is practical for contests, but __int128_t is not standard C++. In production C++20 code, std::midpoint communicates the intent more clearly and has a standard guarantee.

---

A short implementation lab

Spend about 10 minutes building a small midpoint test file.

1. Implement a C++20 version using std::midpoint.
2. Verify these cases with assertions:

assert(std::midpoint(0, 1) == 0);
assert(std::midpoint(-5, -4) == -5);
assert(std::midpoint(4, 5) == 4);

assert(std::midpoint(std::numeric_limits<int>::min(),
                     std::numeric_limits<int>::max()) == -1);

assert(std::midpoint(std::numeric_limits<int>::max() - 1,
                     std::numeric_limits<int>::max())
       == std::numeric_limits<int>::max() - 1);

3. For ordered random int pairs, create a 64-bit reference value:

std::int64_t expected = L + (H - L) / 2;

where L and H are widened copies of the ordered inputs. Check that the result equals std::midpoint(lo, hi).

The key test is not just “does the midpoint lie between the endpoints?” Check its rounding direction as well. A binary-search loop can be correct only when the midpoint convention and updates were designed together.

---

Conclusion

The direct midpoint expression,

(lo + hi) / 2

can overflow before division, even when the final midpoint would fit.

For the nonnegative index ranges in standard binary search, this remains a correct safe form:

lo + (hi - lo) / 2

Its safety follows from the interval contract $0\le \text{lo}\le \text{hi}$, not from an unconditional property of signed arithmetic.

For genuinely arbitrary signed bounds, use C++20’s:

std::midpoint(lo, hi)

It avoids overflow and, when called as std::midpoint(lo, hi) with ordered bounds, supplies the lower midpoint required by your existing half-open templates.

Next, you will bring the pieces together in a formal proof: termination and partial correctness of a boundary-search loop.