二分查找中间元素的Python正确计算方式是什么？

我们逐个分析你列出的几种计算方式：

• mid = low + (high + low)//2：完全错误。展开后等价于 (2*low + high) // 2，计算结果会偏离正确的中间值。比如low=1、high=3时，得到的结果是3，而正确的中间值应为2，完全不符合二分查找的逻辑需求。

• mid = (low + high)/2：不适用。Python中/除法会返回浮点数，而列表索引必须是整数，直接用这个值作为索引会触发TypeError。即便手动转换为整数，也不如直接使用整数运算高效。

• mid = low + (high - low)//2：正确且是推荐写法。它的优势包括：

  1. 避免了low + high可能出现的溢出问题（虽然Python整数无溢出限制，但这个写法在C++等其他语言中同样适用，是跨语言的标准写法）；
  2. 始终返回整数，符合索引的类型要求；
  3. 无论low和high是正数还是负数，都能正确计算出向下取整的中间值。例如low=-5、high=-2时，计算结果为-4，和(low + high)//2的结果一致，完全符合二分查找的逻辑。

• mid = int((high + low)/2)：仅在正数场景下看似正确，但存在隐患。当low + high为负数时，int()的截断行为和Python的整数除法//不同：比如low=-5、high=-2时，(low+high)/2 = -3.5，int(-3.5)得到-3，而正确的中间值应该是-4（向下取整），这会导致二分查找的逻辑出错，因此不推荐使用。

内容的提问来源于stack exchange，提问作者uzHerzeg Herzeg