python - 二进制搜索中的一个错误关闭(极端情况)

Question

在我的二分搜索版本中，我遇到了极端情况的问题。我的版本将输出在输入列表中包含 1 的 bin。该算法通过分别测试输入列表一半大小的组(下面代码中的上部和下部)来实现这一点，如果检测到 1 的存在，该算法将像正常的二进制搜索一样移动引用并继续直到它有找到了 1。该列表仅包含 1 和 0。

注意有人向我指出 any() 将使用 O(n) 操作扫描(子)列表，因此似乎违背了下面算法的目的(即通过测试子来识别 1 的位置)列表)。我正在积极寻找更好的测试，很乐意听到任何想法，但我(目前)对解决这个问题非常感兴趣。

函数如下:

def binary_search(inList):
    low = 0
    high = len(inList)

    while low < high:
        mid = (low + high) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]
        if any(lower):
            high = mid
        elif any(upper):
            low = mid+1
       else:
            # Neither side has a 1
            return -1
    return mid

下面是上面代码通过的单元测试:

# Test a basic case
inlist = [0] * 256
inlist[123] = 1
assert binary_search(inlist) == 123

# Test a case with odd len
inlist = [0] * 99
inlist[20] = 1
assert binary_search(inlist) == 20

# Test a case with odd len
inlist = [0] * 100
inlist[20] = 1
assert binary_search(inlist) == 20

inlist = [0]*4
inlist[1] = 1
assert binary_search(inlist) == 1

# Start
inlist = [0] * 256
inlist[0] = 1
assert binary_search(inlist) == 0

##middle
inlist = [0] * 256
inlist[128] = 1
assert binary_search(inlist) == 128

#end
inlist = [0] * 256
inlist[255] = 1
assert binary_search(inlist) == 255

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

但它在这个极端情况下失败了

inlist = [0]*4
inlist[2] = 1
assert binary_search(inlist) == 2

似乎正在发生的是，在第一阶段一切都按预期进行:

inList = [0,0,1,0]
upper = [1,0]
lower = [0,0]

但是第二阶段mid,high,low都变成3了

upper = [0]
lower = []

即错过了 1。

我在调试器中花了一个小时，并将函数修改为:

def binary_search(inList)
    low = 0
    high = len(inList) -1
    while low <= high:
        mid = low + (high - low) // 2
        if any(inList[low:mid]):    # <- this one
            high = mid - 1
        elif any(inList[mid + 1:high+1]): # <- this one
            low = mid + 1
        else:
            return mid
    return -1

这现在通过了上面的所有测试(以及奇怪的极端情况)，除了全 0 测试:

#Test the case with no 1s
inlist = [0] * 8
assert binary_search(inlist) == -1

我意识到这很愚蠢，但我不知道如何让函数通过这两个测试。

Answer 1

这是你的问题:

while low <= high:
    mid = low + (high - low) // 2
    if any(inList[low:mid]):    # <- this one
        high = mid - 1
    elif any(inList[mid + 1:high+1]): # <- this one
        low = mid + 1
    else:
        return mid

想想当您的列表包含所有 0 时会发生什么。 if 失败，因为 inList 中 low 和 mid 中没有 1 >。 elif 也失败了，因为在 mid 和 high 之间没有 1。然后是else，也就是现在执行的内容。因此，您不会得到 -1。

您的else block 正是当inList 中没有1 时执行的代码部分。因此，如果你真的想处理所有 0 的情况，那么你应该让该 block 返回 -1

不过作为旁注，我不确定您为什么要对未排序的列表执行类似于二进制搜索的操作。