Why do some codes in Binary Search set the middle pivot as 'left (right

For example, basic binary search in 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

In this code, pivot is left (right - left) // 2, not len(nums) // 2. Could you explain why?

CodePudding user response：

len(sums)//2 is never interchangeable with left (right - left) // 2. They are different things. But there is (left right) // 2 which may be what you are confused about.

left (right - left) // 2 and (left right) // 2 are basically the same except for one thing: The latter can overflow due to the fact that we first add left and right and then divide. Integer overflow is not possible in Python but this can happen in languages like C and Java where the size of an integer is limited.

Read this article about how this bug is prevalent in many code bases.