Karthik Blog Binary search is a cool way to search for a number in a sorted sequence of numbers. Its O(log n) time complexity and just needs 3 pointers, a left, a right and a mid pointer which is calculated using the left and right. The calculation of the midpoint is pretty simple too, just add the left and right pointer index and do a floor division by 2.
int mid = floor((left + right) / 2);However when your left and right pointers are extremely big and you add them together, it will cause an integer overflow. There’s a maximum integer size that can be stored by the computer. For signed 32-bit integers, the range is -2,147,483,648 to 2,147,483,647.
So if left = 2,000,000,000 and right = 2,000,000,000, then left + right = 4,000,000,000 🧨 OVERFLOW
I also noticed that different data types in c++ handle this differently.
| Type | Overflow Behavior | Description |
|---|---|---|
| int / long | ❌ Undefined Behavior | Dangerous! Leads to bugs or optimizations that break logic |
| unsigned int | ✅ Defined (Wraparound) | Safe, wraps modulo 2ⁿ |
| float / double | ✅ Defined | Overflows to +∞, underflows to 0 or -∞ |
This shouldnt be an issue in python though since integers have arbitrary precision which means they grow in size as needed, using as much memory as required. It can automatically switches from a 32-bit or 64-bit representation to a “bignum” object. Internally it uses fixed-width integers (like C longs) for small values and when the number gets too big, it switches to a variable-size bigint format transparently. Its slower than C++ fixed-size math, but it’s safe and convenient.
*Do note that in python floats still have overflow
So moving on to the problem at hand, how do we fix this. Simple, just use this:
int mid = left + (right - left) / 2;holdup ✋. why does this work ?? basically it just uses subtraction and one addition, and never adds two large numbers together, avoiding overflow.
Well, to show it algebraically,
and now you know how to binary search better.