python - 终止条件为 `left < right` 时的二分查找，步长更新为 `left = mid +1, right = mid`

Question

我正在阅读 Binary Search Template II in leetcode :

It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor's index in the array.

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:

只是:

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

测试:

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对模板的总结(打不开链接可以引用):

Key Attributes:

• An advanced way to implement Binary Search.
• Search Condition needs to access element's immediate right neighbor
• Use element's right neighbor to determine if condition is met and decide whether to go left or right
• Gurantees [sic] Search Space is at least 2 in size at each step
• Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

Distinguishing Syntax:

• Initial Condition: left = 0, right = length
• Termination: left == right
• Searching Left: right = mid
• Searching Right: left = mid+1

Answer 1

与循环在满足 lo > hi 时立即终止的二进制搜索的规范版本相反，在这种情况下，循环在 lo == hi 时终止。但是由于元素 nums[lo](也是 nums[hi])也必须被检查，所以在循环之后添加额外的检查。

保证循环仅在lo == hi时终止，因为向左移动包含了以后搜索中的mid元素(else: right = mid) 而在规范版本中，mid 元素在两种情况下都被排除在未来的搜索之外