二进制搜索关闭 1 个无限循环

Question

所以我有以下二进制搜索算法，有时运行进入无限循环：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums)-1
        mid = (j+i)//2
        while i<j: 
            if nums[mid] == target:
                return mid
            if nums[mid] > target: 
                j = mid
                mid = (j+i)//2
            else: 
                i = mid
                mid = (j+i)//2                
        
        return mid if nums[mid] == target else -1

正确的版本是 j = mid+1 和 i = mid-1。在某些情况下，如果中间指针不在 i 和 j 所限定的区间内，上面的代码将运行陷入无限循环。为什么会发生这种情况，更重要的是，为什么不同的分配会阻止这种情况发生？

一个示例测试用例是：

nums = [-1,0,3,5,9,12], target = 2

Answer 1

使用您的示例测试用例，第二次迭代给出：

i = 0、j = 2 和 mid = 1

然后在第 3 次迭代时，它给出：

i = 1、j = 2 和 mid = 1

如果你进一步跟踪它，mid = 1 将是重复的结果，因为 i 总是 1 而 j 总是 2。这就是无限循环的原因。

这是一个重构版本，它捕获了您提供的边缘情况：

nums = [-1, 0, 3, 5, 9, 12]
target = 2


def search(nums: List[int], target: int) -> int:
    i, j = 0, len(nums)-1
    mid = (j+i)//2
    while i < j:
        print(i, j, mid)
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            j = mid
            mid = (j+i)//2
        elif nums[mid] < target and nums[mid+1] < target:
            i = mid
            mid = (j+i)//2
        else:
            return -1

    return mid if nums[mid] == target else -1

我会进一步重构它以变得更简单和可读：

def search(nums: List[int], target: int) -> int:
    i, j = 0, len(nums)-1
    while i < j:
        mid = (i+j)//2
        if nums[mid] < target:
            i = mid+1
        elif nums[mid] > target:
            j = mid-1
        else:
            return mid
    return -1

解释：如果nums[mid]>target，我们忽略右半部分，反之亦然。如果我们的索引已经收敛（即 i==j），但我们仍然没有找到目标，return -1

Answer 2

进行不产生无限循环的二分搜索的规则是确保每种情况总是缩小搜索范围 space。由于您已经选中 mid，因此您可以设置边界，使其不再包含在范围内。您还可以简化代码以在循环顶部计算 mid，这样您就不会在每种情况下都重复计算。

    def search(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums)-1
        while i<j:
            mid = (j+i)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target: 
                j = mid - 1
            else: 
                i = mid + 1
        
        return i if nums[i] == target else -1

二进制搜索关闭 1 个无限循环

Binary Search Off By 1 Infinite Loop

algorithm

search

binary-search