3

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

注意有人向我指出 any() 将使用 O(n) 操作扫描 (sub) 列表，因此似乎违背了下面算法的目的（即通过测试 sub 来识别 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

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

4

3 回答 3

2

这是你的问题：

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

想想当你的列表包含所有0s 时会发生什么。失败，因为和之间if没有1s 。也失败了，因为和之间没有s 。然后是一个，这正是现在执行的。因此，您没有得到.inListlowmidelif1midhighelse-1

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

不过，作为旁注，我不确定您为什么要在未排序的列表上做任何类似于二进制搜索的事情。

于 2013-07-16T17:43:03.180 回答
1

用二分搜索解决你的任务是不可能的。在底部查看我的评论。但是，您几乎正确地实现了二进制搜索，所以让我们修复它，然后讨论为什么它不适合这个问题。

这是带有注释的固定版本（原始版本的）。整体结构很好，这些只是一点点的问题：例如，您应该设置low为mid而不是，mid+1否则如果 1 在mid.

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

    while low < high - 1:  # Iterate while there are at least 2 elements
        mid = (low + high) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]
        if any(lower):
            high = mid
        elif any(upper):
            low = mid  # mid was the first element in upper, so make sure to keep it
        if low == high - 1:
            # Only one element remains now, so it must be the 1
            return low
    return -1

但是，正如您所指出的，当您运行 any() 时，您正在扫描列表，这否定了二进制搜索的全部意义。

二进制搜索是一种无需查看列表中的每个元素即可在列表中查找内容的方法。这怎么可能呢？仅当列表已排序时。二进制搜索重复地将列表分成两半，就像你正在做的那样，但只是通过查看mid而不检查lowerand upper。

于 2013-07-16T17:48:53.870 回答
1

修复你的程序

您可以像这样“修复”您的程序：

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

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

我将循环条件更改为“while low + 1 < high”，重新分配为“low = mid”（而不是 low = mid + 1），结果为“返回低”。这通过了您的测试。

这样做的原因是您定义它的方式，低，中和高更好地理解为边界而不是索引：

  item 0 item 1 item 2 item 3 item 4 item 5 item 6 item 7 item 8
 |______|______|______|______|______|______|______|______|______|
 0      1      2      3      4      5      6      7      8      9
low                         mid                                high

当您将列表分成两部分时，您会得到如下两部分：

  item 0 item 1 item 2 item 3 
 |______|______|______|______|
 0      1      2      3      4
low                         mid

  item 4 item 5 item 6 item 7 item 8
 |______|______|______|______|______|
 4      5      6      7      8      9
mid                                high

如果您确定目标值位于上半部分，则它可能位于这五个索引中的任何一个中。设置 low = mid + 1 没有意义，因为这忽略了 item #4 是目标 item 的可能性。

最终，该算法会将其缩小到一个项目的范围。与您的旧算法不同，低永远不会等于高。所以我们在低 + 1 == 高时停止，结果是低。（注意 mid 还没有更新。low 是我们想要的索引。）

二进制搜索

这不是人们谈论二分搜索算法时的意思！二进制搜索应用于排序列表以查找具有目标值的元素，而无需比较列表中的每个元素。您不能将二进制搜索应用于未排序的列表。想一想——根本不知道去哪里找——你必须检查列表中的每一项，直到找到目标。您的算法实际上比线性搜索慢，因为它会多次扫描列表中的每个项目！

于 2013-07-16T17:52:24.037 回答