Why Use mid = left + (right-left) / 2 Instead of mid = (left+right) / 2 to Calculate the Midpoint in Binary Search

Using `mid = left + (right — left) / 2` instead of `mid = (left + right) / 2` helps to prevent potential overflow errors. Let’s delve into the details:

Avoiding Overflow
When calculating the midpoint using `(left + right) / 2`, if `left` and `right` are very large integers, their sum can exceed the maximum value that can be stored in an integer variable (typically `INT_MAX` in many programming languages). This overflow can lead to incorrect calculations and unexpected behavior.

Example of Potential Overflow
Consider the maximum value for a 32-bit signed integer, `INT_MAX`, which is 2,147,483,647. If `left` and `right` are both close to `INT_MAX`, their sum will exceed the maximum representable integer value, causing an overflow. (INT_MAX = “2,147,483,647” Maximum value for a variable of type int)

int left = 2147483646;
int right = 2147483647;
int mid = (left + right) / 2; // Potential overflow

In the above example, `left + right` would be 4,294,967,293, which is greater than `INT_MAX`. This would result in an overflow, causing the calculation to yield an incorrect result.

Safe Midpoint Calculation
To avoid this problem, we use the alternative formula:

```cpp
int mid = left + (right — left) / 2;
```

This approach ensures that we never directly add `left` and `right`, thus preventing overflow.

Why This Works
The expression `left + (right -left) / 2` effectively calculates the same midpoint but in a safer way:
- `right — left` will always be a non-negative integer within the range of representable integers, so there’s no risk of overflow here.
- Adding `left` to the result of `(right - left) / 2` will not overflow as long as `left` and `right` are within the range of representable integers.

Example Using Safe Midpoint Calculation
Using the same values for `left` and `right`:

```cpp
int left = 2147483646;
int right = 2147483647;
int mid = left + (right — left) / 2; // Safe calculation
```

Here, `right - left` equals 1, so ` (right -left) / 2` equals 0. Adding this to `left` results in `2147483646`, which is the correct and safe midpoint.

Conclusion
Using `mid = left + (right - left) / 2` is a well-known technique to avoid overflow and ensure that the midpoint calculation is safe and accurate, especially when dealing with large integer values.