In Binary search why doing mid = (left + (right - left)) // 2 is better than mid = (left + right) // 2?

Question

In a binary search while loop:

left, right = 0, len(nums)
while left < right:
    mid = (left + right) // 2
    if nums[mid] == target:
        return mid

Why doing mid = (left + (right - left)) // 2 is better than doing mid = (left + right) // 2 in some languages other than python?

Edit: Seems like I got the parentheses wrong. Thanks for pointing that out and it clears it up more for me. I will leave it like this in case someone else stumbles upon this. I saw this remark in a youtube video, but the person never explained why one would be better than the other. Thank you all for answering!

Thanks, Everyone!

Is this something you read from some other source? You should link to it — Alexander, Oct 25 '21 at 14:37
Agreed with @user2390182 that you mean mid = left + (right - left) // 2, which helps to avoid overflows. — Andrew Holmgren, Oct 25 '21 at 14:40
Does this answer your question? [Midpoint Formula Overflow Error](https://stackoverflow.com/questions/24317360/midpoint-formula-overflow-error) — Andrew Holmgren, Oct 25 '21 at 14:41
If it means what @user2390182 is saying then the answer is left+right may overflow. https://cs.stackexchange.com/questions/80415/why-is-binary-search-using-this-weird-thing-to-calculate-middle. but that isn't a problem in python — Equinox, Oct 25 '21 at 14:41

score 4 · Accepted Answer · answered Oct 25 '21 at 14:41

In Python, neither is better. Or rather, (left + right) // 2 is very slightly better because it does one fewer arithmetic operation. But this is negligible.

In other languages, left + (right - left) // 2 would be used to avoid integer overflow, which could happen when doing left + right. This can't happen in Python because Python natively allows for arbitrarily large integers; so the advice you saw is not relevant to Python.

score 2 · Answer 2 · answered Oct 25 '21 at 14:40

left + right can overflow if the values are too high for their int representation. See Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken for details.

This is an issue in languages like C, where int variables have a limit, but not in Python. You should be fine using the more straightforward code.

score 0 · Answer 3 · answered Oct 25 '21 at 14:40

Well, you got the parentheses wrong. I'll let you figure that out.

But to answer your question:

In Python it doesn't matter, because integers can grow as large as needed.

In other languages, where there is a limit on the size of integers, it is possible that left + right will overflow, whereas the alternate calculation will not.

score 0 · Answer 4 · answered Oct 25 '21 at 14:46

That is done to handle the overflow of numbers sum in languages such as C and C++. You have a limit on the integer range. In

                int mid = (low+high)/2;

We calculate the sum first and divide later, which might overflow buffer for large values of low and high.

This overflow condition is handled by calculating the difference first and then dividing the difference and adding low to it. Which results in,

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

In Binary search why doing mid = (left + (right - left)) // 2 is better than mid = (left + right) // 2?

4 Answers4