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

user_10111105 0
Viewed 390

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!

binary-search python
4 Answers

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.

user_122990000
Bill_the_Lizard_12880

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.

user_4488100

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;
user_160180950
Related