Search code examples
pythonbinary-search

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


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!


Solution

  • 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.