1

我在实现二进制搜索的修改版本时遇到了一些困难（它只需要检查子列表中是否有 1，然后继续搜索直到它返回索引）。

目前我想出的代码是：

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

        assert low < high
    return -1

它似乎适用于循环的几次迭代，但随后它返回空列表并失败。我已经使用以下输入测试了该功能：

l = [0 for x in range(256)]
l[123] = 1

我还注意到，当列表被抽取时，一些垃圾箱会丢失。

我将如何着手创建一个测试套件，它将捕获这些问题并让我将此算法扩展到其他输入集（例如，两半中的 1，彼此相邻的两个 1 等）。

4

3 回答 3

2

伙计，你问的是三个问题，但这里什么都没有。

要创建测试套件，只需编写一些好的示例并断言它们有效，例如：

from binary_search import binary_search

# 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 the case with no 1s
inlist = [0] * 256
assert binary_search(inlist) == -1

# It's good to test corner cases just in case
inlist = [0] * 256
inlist[0] = 1
assert binary_search(inlist) == 0
inlist = [0] * 256
inlist[255] = 1
assert binary_search(inlist) == 255

您可能需要考虑使用诸如鼻子或单元测试模块之类的东西来帮助您组织测试，但无论如何，我们的想法是每次更改代码时都运行测试以确保其正常工作。如果您在代码中添加新功能，例如允许在列表中搜索多个 1，您将需要为该行为添加测试。

您可能已经知道这一点，但以防万一我想说这是在列表中查找 1 的一个非常糟糕的算法。问题是这any是一个 O(N) 操作，因此在循环的每次迭代中，您都在执行 N/2 或 N 个操作。循环运行 log(N) 次。涉及到一些数学，但您可以很容易地证明这是一个 O(N*log(N)) 算法，而只需使用inlist.index(1)（或基本的 for 循环），您就可以在 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

    assert low == high
    return mid

您的版本的主要问题是您同时修改了低/高和修改 inlist。因为低/高是 inlist 的索引，所以当您修改 inlist 时，它们不再指向正确的位置。

于 2013-07-03T12:36:03.313 回答
2

您可以构建一个简单的测试套件，使用unittest它可以测试不同输入的结果，对于这个例子来说应该很简单。

这应该让你开始 - 尝试运行这个脚本（在修改导入以导入你的二进制搜索模块之后），谷歌python unittest应该会给你很多关于如何扩展它的想法。

import unittest

from <your module> import binary_search

class TestBinarySearchForOne(unittest.TestCase):

    def test_small_range(self):
        self.assertEquals(1, binary_search(range(0, 2))

    def test_not_found(self):
        self.assertEquals(-1, binary_search([0, 4, 9, 190])

if __name__ == '__main__':
    unittest.main()
于 2013-07-03T12:25:07.013 回答
1

我不明白你到底想做什么；您只需要更改“经典”算法中的两行，如Wikipedia中给出的：

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

这对我有用：

>>> binary_search(l)
123
于 2013-07-03T12:34:38.540 回答