ProblemsUB & GotchasThe midpoint that overflows
IntermediateUB & Gotchas

The midpoint that overflows

Context

A code review from someone who's 'always written it this way': mid = (lo + hi) / 2. Worked for twenty years! Then the inputs grew toward INT_MAX, the sum overflowed, and the search wandered into negative indices. UB doesn't age — it waits. Rewrite the midpoint so it cannot overflow, staying in plain int.

Task

The textbook midpoint (a + b) / 2 is a famous bug: for large operands a + b overflows, and signed integer overflow is undefined behaviour. Fix midpoint so it is correct for every pair of ints.

Constraints

  • Must return the mathematical midpoint, rounded toward zero like integer division
  • Must not overflow for any int inputs — no signed overflow (UBSan must stay clean)
  • Must remain correct for negative and mixed-sign inputs
  • Do not widen to long long / int64 — solve it in int arithmetic

Before you code

  • Why is signed integer overflow undefined behaviour, not just "wraps around"?
  • How does a + (b - a) / 2 avoid the overflow that (a + b) / 2 hits?
  • Does your fix still round the same way for negative results?

Tests

  • #1Large operands must not overflow (the gotcha)
  • #2Basic midpoints
  • #3Negative and mixed-sign inputs

Hints

Hint 1

a + (b - a) / 2 computes the same midpoint but only ever adds a half-distance to a, so it cannot overflow.

Editorfix-the-overflow.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.