Overflow-safe midpoint and running mean
Two innocuous-looking averages hide a real bug in fixed-width languages:
- The midpoint of two indices
loandhiin binary search, usually written(lo + hi) // 2. - The mean of a long array of large numbers, usually written
sum(xs) / len(xs).
Both can overflow a 32- or 64-bit integer when the individual values are far below the limit but their sum is not.
Write overflow-safe versions of both, and explain when the naive code is actually wrong.
Show a hint
For the midpoint, you never need the full sum lo + hi, only its half. Rewrite it so the largest intermediate value is at most hi. For the array mean, avoid ever holding the whole sum: update an average incrementally.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.