`mid = low + (high -low)//2` 与 `(low + high)//2`

Question

我正在研究树问题Convert Sorted Array to Binary Search Tree - LeetCode给定一个元素按升序排序的数组，将其转换为高度平衡的 BST。对于这个问题，高度平衡二叉树被定义为一个二叉树，其中每个节点的两个子树的深度相差永远不会超过 1。例子：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直观的 D&Q 解决方案是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设置为len(nums)//2或(low + high)//2当阅读其他提交时，我发现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 rootmid 被设置为 mid = low + (high -low)//2mid = low + (high -low)//2超过有(low + high)//2什么好处？

Answer 1

这是一种避免整数溢出的模式；该代码可能是从具有固定大小整数的语言移植而来的。当索引可以变得与用于包含它们的类型一样大时，中间low + high值的溢出就会成为一个问题，导致未定义的行为、错误的结果和漏洞。（这甚至会发生在大整数类型中，例如size_t当您搜索不是数组的内容时。）

… 但在 Python 中，没有整数溢出，所以你是对的，你可以只做(low + high) // 2.

Answer 2

在许多语言中，例如 C++、JAVA。整数有固定的取值范围，例如：

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

有时在有效范围内的低和高，但low + high可能会溢出。

所以使用差异更安全 mid = low + (high -low)//2

但对于 python 来说不是必需的，因为它的工作方式类似于BigIntegerJava。