努力使用递归代码对分搜索字符串

Question

所以我要在线 python class。我想帮助找出我的代码和正确答案代码之间的差异。我没有注释我的答案，但答案已注释，您需要的每一件事都应该在那里弄清楚我想做什么。我一开始是自己写的答案，结果和class给出的正确答案码很像。但是，我的代码一直返回错误

Traceback (most recent call last):
  File "submission.py", line 11, in isIn
    middle = aStr[midIndex]
IndexError: string index out of range

这是我的代码

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string

    returns: True if char is in aStr; False otherwise
    '''
    # Your code here
    midIndex = len(aStr)//2 
    middle = aStr[midIndex]

    if len(aStr) == 0:
        return False
    if len(aStr) == 1 or char == middle:
        return True
    else:
        if char > middle:
            return isIn(char,aStr[:middle])
        else:
            return isIn(char,aStr[middle +1:])

这是class给我的正确答案：

def isIn(char, aStr):
   '''
   char: a single character
   aStr: an alphabetized string

   returns: True if char is in aStr; False otherwise
   '''
   # Base case: If aStr is empty, we did not find the char.
   if aStr == '':
      return False

   # Base case: if aStr is of length 1, just see if the chars are equal
   if len(aStr) == 1:
      return aStr == char

   # Base case: See if the character in the middle of aStr equals the 
   #   test character 
   midIndex = len(aStr)//2
   midChar = aStr[midIndex]
   if char == midChar:
      # We found the character!
      return True

   # Recursive case: If the test character is smaller than the middle 
   #  character, recursively search on the first half of aStr
   elif char < midChar:
      return isIn(char, aStr[:midIndex])

   # Otherwise the test character is larger than the middle character,
   #  so recursively search on the last half of aStr
   else:
      return isIn(char, aStr[midIndex+1:])

midIndex 对于我的代码是 middle_nummber 而 midChar 对于我的代码只是 middle.

Answer 1

您的版本有4个错误；两个负责处理边缘情况，另外两个负责确定要搜索的一半。

您的代码没有正确处理 'empty string' 案例。对于长度为 0 的字符串，midIndex 将是 0，但 aStr[0] 将不存在。

这就是为什么带注释的答案从开始

if aStr == '':
    return False

如果输入为空，则无法找到搜索到的字符串。您确实对这种情况进行了测试，但为时已晚。这就是导致您共享回溯的原因：

>>> aStr = ''
>>> midIndex = len(aStr)//2
>>> midIndex
0
>>> aStr[midIndex]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: string index out of range

接下来，您也错误地处理了 len(aStr) == 1 边缘情况。您的测试是：

if len(aStr) == 1 or char == middle:
    return True

如果aStr设置为'z'，则len(aStr)为真，char设置为什么无关紧要。所以 aStr = 'z';char = 'a', will produceTrue` 来自你的函数，这显然是不正确的：

>>> aStr = 'z'
>>> char = 'a'
>>> middle = 'z'
>>> len(aStr) == 1 or char == middle
True

正确答案只是简单地测试长度为 1 的情况下 aStr == char 是否为真；我会坚持这一点，或者至少将 or 替换为 and:

>>> len(aStr) == 1 and char == middle
False
>>> char = 'z'
>>> len(aStr) == 1 and char == middle
True

你的下一个错误在你搜索的那一半。你测试：

if char > middle:

所以搜索到的字符比中点大。您想要在已排序输入字符串的第二个上半部分进行搜索。相反，您的版本在对面搜索，下半部分：

if char > middle:
    return isIn(char,aStr[:middle])  # slicing up to the middle

使用数字而不是字母来更好地说明这一点，输入字符串 '12345' 有一个中点 '3'，因此如果 char 是 '4' 或 '5'，你想在下半场找到它。

您的第 4 个也是最后一个错误在 aStr[:middle] 表达式中。 middle 是单个字符，不是整数索引。你想使用 midIndex:

if char > middle:
    return isIn(char, aStr[:midIndex])
else:
    return isIn(char, aStr[midIndex + 1:])

努力使用递归代码对分搜索字符串

Struggling with recursive code to bisection search a string

python

bisection