二分查找，终止条件为“left < right”，步长更新为“left = mid +1，right = mid”

我正在读leetcode中的二分查找模板二:

它用于搜索需要的元素或条件访问当前索引及其直接右邻居的索引在数组中。

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # Post-processing:
    # End Condition: left == right
    if left != len(nums) and nums[left] == target:
        return left
    return -1

我觉得额外的条件and nums[left] == target是不必要的。

改变时：

if left != len(nums) and nums[left] == target:

to just:

if left != len(nums):

...它工作完美：

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # Post-processing:
    # End Condition: left == right
    if left != len(nums):
        return left
    return -1

Tests:

In [4]: nums = list(range(100))             

In [5]: binarySearch(nums, 55)              
Out[5]: 55

In [6]: binarySearch(nums, 101)             
Out[6]: -1

In [7]: binarySearch(nums, 38)              
Out[7]: 38

什么原因nums[left] == target应该添加？

Leetcode对模板的总结（如果打不开链接可以参考）：

关键属性：

• 实现二分查找的高级方法。
• 搜索条件需要访问元素的直接右邻居
• 利用元素的右邻居来判断是否满足条件并决定向左还是向右
• 保证 [原文如此] 每一步的搜索空间大小至少为 2
• 需要后处理。当剩下 1 个元素时，循环/递归结束。需要评估剩余元素是否满足 健康）状况。

区分语法：

• 初始条件：left = 0, right = length
• 终止：left == right
• 向左搜索：right = mid
• 搜索权：left = mid+1

与二分搜索的规范版本相反，其中循环一旦终止lo > hi满足，在这种情况下循环终止lo == hi。但由于元素nums[lo]（这也是nums[hi]) 也必须进行检查，额外的检查是在循环之后添加的。

保证循环仅在且仅当lo == hi，因为向左移动包括mid未来搜索中的元素（else: right = mid）在规范版本中，mid在这两种情况下，元素都被排除在未来的搜索之外