为什么Binary Search 中的某些代码将中间枢轴设置为'left + (right - left) //2'？

Question

例如，Python中的基本二分查找：

left, right = 0, len(nums) - 1

while left <= right:
    # // 2 -> floor
    pivot = left + (right - left) // 2
    if nums[pivot] == target:
        return pivot
    if target < nums[pivot]:
        right = pivot - 1
    else:
        left = pivot + 1

在此代码中，主元是 left + (right - left) // 2，而不是 len(nums) // 2。你能解释一下为什么吗？

Answer 1

len(sums)//2 永远不能与 left + (right - left) // 2 互换。它们是不同的东西。但是有一个(left + right) // 2可能是你困惑的地方

left + (right - left) // 2 和 (left + right) // 2 除了一件事基本相同：后者可能会溢出，因为我们首先添加 left 和 right 然后划分。在 Python 中不可能发生整数溢出，但在 C 和 Java 等语言中可能会发生整数溢出，其中整数的大小是有限的。

Read this article 关于此错误在许多代码库中的普遍性。

为什么Binary Search 中的某些代码将中间枢轴设置为'left + (right - left) //2'？

Why do some codes in Binary Search set the middle pivot as 'left + (right - left) //2'?

python

algorithm

binary-search