使用元组的二进制搜索迭代和递归 (python)

Question

我正在尝试创建一个二进制搜索（迭代和递归），参数为 (tuple, int)。我真的很想更深入地了解它，因为我认为我按原样从逻辑上理解了代码，但显然不是。

迭代代码 (isMemberI) 有一半的时间给我正确的结果，然后随机地给出错误的结果，所以我不知道是什么原因造成的。我没有收到任何错误，只是有时回答错误。

递归代码有时会给我错误，然后可能在我的测试用例中工作了 ¼。当我尝试以下操作时，出现以下错误：

>>> isMemberR((1, 2, 3, 3, 4), 4
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    isMemberR((1, 2, 3, 3, 4), 4)
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 127, in     isMemberR
    return isMemberR(aseq[midpoint + 1], target)
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 117, in isMemberR
    if len(aseq) == 0:
TypeError: object of type 'int' has no len()

>>> isMemberR('aeiou', 'y')
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    isMemberR('aeiou', 'y')
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 127, in isMemberR
    return isMemberR(aseq[midpoint + 1], target)
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 127, in isMemberR
    return isMemberR(aseq[midpoint + 1], target)
IndexError: string index out of range


>>> isMemberR((1, 3, 5, 7), 4)
Traceback (most recent call last):
  File "<pyshell#4>", line 1, in <module>
    isMemberR((1, 3, 5, 7), 4)
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 125, in isMemberR
    return isMemberR(aseq[:midpoint], target)
  File "/Users/alyssakelley/Documents/p93_binsearch.py", line 127, in isMemberR
   return isMemberR(aseq[midpoint + 1], target)
IndexError: tuple index out of range

这是我的代码：

def isMemberI(aseq, target):
    first = 0
    last = len(aseq) - 1
    found = False

    while first < last:
        midpoint = (first + last) // 2
        if aseq[midpoint] == target:
            found = True

        else:
            if target < aseq[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found 

def isMemberR(aseq, target):
    if len(aseq) == 0:
        return False
    else:
        midpoint = len(aseq) // 2
        if aseq[midpoint] == target:
            return True
        else:
            if target < aseq[midpoint]:
                return isMemberR(aseq[:midpoint], target)
            else:
                return isMemberR(aseq[midpoint + 1], target)

我正在尝试的测试用例和结果我 EXPECT :

>>> isMemberI((1, 2, 3, 3, 4), 4)
True

>>> isMemberI((1, 2, 3, 3, 4), 2)
True

>>> isMemberI('aeiou', 'i')
True

>>> isMemberI('aeiou', 'y')
False

>>> isMemberI((1, 3, 5, 7), 4)
False

>>> isMemberI((23, 24, 25, 26, 27), 5)
False

>>> isMemberI((0, 1, 4, 5, 6, 8), 4)
True

>>> isMemberI((0, 1, 2, 3, 4, 5, 6), 3)
True

>>> isMemberI((1, 3), 1)
True

>>> isMemberI((2, 10), 10)
True

>>> isMemberI((99, 100), 101)
False

>>> isMemberI((42,), 42)
True

>>> isMemberI((43,), 44)
False

>>> isMemberI((), 99)
False
'''

Answer 1

这里最后一个函数调用是在索引 midpoint+1 处传递一个值而不是元组。

错误解释

IndexError: tuple index out of range ，当 len of tuple 为 1 且 midpoint+1 为 1 超出范围，因为只有一个元素

TypeError: object of type 'int' has no len() ，那时候 int 被传递在最后一行作为 isMemberR

的第一个论点

def isMemberR(aseq, target):
    if len(aseq) == 0:
        return False
    else:
        midpoint = len(aseq) // 2
        if aseq[midpoint] == target:
            return True
        else:
            if target < aseq[midpoint]:
                return isMemberR(aseq[:midpoint], target)
            else:
                return isMemberR(aseq[midpoint+1:], target)

使用元组的二进制搜索迭代和递归 (python)

Binary Search Iterative and Recursive with tuple (python)

python

recursion

binary-search