Binary Search: Understanding the Overflow Trap

When implementing binary search, a common mistake is calculating the midpoint as:
mid = (low + high) / 2;

At first glance, this might seem correct and intuitive. However, this approach can lead to a critical bug.

To avoid this, use the safer formula: mid = low + (high - low) / 2;

Let's understand why

To do this, we need to revisit binary numbers and understand integer ranges. Typically, an int is 4 bytes = 32 bits, where each bit stores a 0 or 1.
So, the maximum value it can hold
(for signed integers) is approximatapproximately: 2^31 - 1 = 2,147,483,647 ≈ 2.1 × 10^9 = 2.1 billion
(one bit is reserved for the sign in a signed integer)

(for unsigned integers) is 2^32 - 1 ≈ 4.29 × 10^9 = 4.29 billion

If we add two large integers whose sum exceeds this limit, an overflow occurs.
This causes the value to wrap around into the negative range or produce unpredictable results, leading to bugs or program crashes.

You can run the following C++ code to understand the overflow problem.

#include <iostream>

int main() {
    int low = 2000000000; // 2 billion
    int high = 2100000000; // 2.1 billion

    // Naive midpoint calculation (may overflow)
    int mid_naive = (low + high) / 2;

    // Safe midpoint calculation (no overflow)
    int mid_safe = low + (high - low) / 2;

    std::cout << "Naive midpoint calculation: " << mid_naive << std::endl;
    std::cout << "Safe midpoint calculation: " << mid_safe << std::endl;

    // Additional check to show what happens if low+high exceeds int max
    long long sum = (long long)low + (long long)high;
    std::cout << "Sum using long long (no overflow): " << sum << std::endl;

    return 0;
}

Now let's connect the dots with the binary search low and high range:

Imagine both low and high are near 2 billion:

int low = 2000000000; // 2 billion ≈ 2 × 10^9
int high = 2100000000;

Naive way:

int mid2 = (low + high) / 2;

Calculation:
mid2 = (2,000,000,000 + 2,100,000,000) / 2
\= 4,100,000,000 / 2
\= 2,050,000,000

As you can see, low + high = 4,100,000,000 exceeds the maximum value for a 32-bit signed int and causes overflow. The result will not be 4.1 billion but some incorrect or negative value, as shown in the code block above. Dividing by 2 afterward won't correct the overflowed value; it remains incorrect.

Safe way:

int mid1 = low + (high - low) / 2;

Calculation:
mid1 = 2,000,000,000 + (100,000,000 / 2)
\= 2,000,000,000 + 50,000,000
\= 2,050,000,000

The safe method, low + (high - low) / 2, prevents overflow because (high - low) is small enough to fit safely within the int range. This completely avoids overflow.

SUMMARY:

Final Thoughts: Using low + (high - low) / 2 is a small but crucial optimization that prevents bugs in binary search implementations, especially when working with large arrays or index ranges