What's the benefits of `mid = low + (high -low)//2` over `(low + high)//2`?

Question

I am working on a Tree problem Convert Sorted Array to Binary Search Tree - LeetCode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

An intuitive D&Q solution is

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        """
        Runtime: 64 ms, faster than 84.45%
        Memory Usage: 15.5 MB, less than 5.70% 
        """
        if len(nums) == 0: return None
        #if len(nums) == 1: return TreeNode(nums[0])
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        if len(nums) == 1: return root 
        if len(nums) > 1: 
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

mid is set as len(nums)//2 or (low + high)//2

When read other submissions, I found

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self.buildBST(nums, 0, len(nums))

    def buildBST(self, nums, left, right):
        if right <= left:
            return None
        if right == left + 1:
            return TreeNode(nums[left])

        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])
        root.left = self.buildBST(nums, left, mid)
        root.right = self.buildBST(nums, mid + 1, right)

        return root

mid was set as mid = low + (high -low)//2

What's the benefits of mid = low + (high -low)//2 over (low + high)//2?

My guess is that it was ported from a language with fixed-size integers, where that approach avoids integer overflow when you have really big arrays. In Python, you don’t have to worry about that. — Ry-, Apr 10 '19 at 11:58

score 4 · Accepted Answer · answered Apr 10 '19 at 12:44

It’s a pattern to avoid integer overflow; the code was probably ported from a language with fixed-size integers. When the indexes can get as big as the types used to contain them, overflow of the intermediate low + high value becomes a problem, leading to undefined behaviour, incorrect results, and vulnerabilities. (This even happens with large integer types like size_t when you’re searching something that’s not an array.)

… But in Python, there is no integer overflow, so you’re right that you can just do (low + high) // 2.

score 1 · Answer 2 · answered Apr 10 '19 at 12:42

in many language, such as C++, JAVA. integer has fixed value range, such as:

int32: -2147483648 ~ 2147483647
int64: -9223372036854775808 ~ 9223372036854775807

sometimes low and high in valid range, but low + high may overflow.

so it is safer to use difference like mid = low + (high -low)//2

but it is not necessary for python, because it works like BigInteger in Java.

What's the benefits of `mid = low + (high -low)//2` over `(low + high)//2`?

2 Answers2