IntermediateMath for DSABinary Search
The safe midpoint: lo + (hi − lo) // 2
(lo + hi) / 2 can overflow in Java and C++ when both are large. lo + (hi − lo) / 2 gives the same middle and never overflows.
The idea
In languages with 32-bit ints, lo + hi can exceed 2³¹ − 1 even when both fit, and the sum wraps to a negative number. hi − lo is never larger than the range itself, so lo + (hi − lo) / 2 is always safe.
Python ints don't overflow, but the habit matters in interviews, and the formula also makes the rounding explicit: it rounds toward lo.
Worked example
lo = 2,000,000,000 and hi = 2,100,000,000 in Java
- lo + hi = 4,100,000,000 > 2,147,483,647 → overflows to a negative number → index error.
- hi − lo = 100,000,000 → / 2 = 50,000,000 → lo + that = 2,050,000,000. Correct.
In code (Python)
def first_bad_version(n, is_bad):
lo, hi = 1, n
while lo < hi:
mid = lo + (hi - lo) // 2 # same as (lo + hi) // 2, overflow-safe
if is_bad(mid):
hi = mid
else:
lo = mid + 1
return loO(log n), unchanged.
How to spot it
- Any binary search on large ranges: indices up to 2³¹, or searching over answer values like 1..10⁹.
Common mistakes
- Fixing overflow with (lo + hi) >>> 1 in Java and then porting it to C++, where >>> doesn't exist.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →