python - 努力使用递归代码来二分搜索字符串

Question

所以我在网上上python课。我想帮助找出我的代码和正确答案代码之间的差异。我没有注释我的，但答案是注释的，你需要的每一件事都应该在那里弄清楚我想要做什么。我一开始是独立写答案的，结果与班级给出的正确答案代码非常相似。但是，我的代码不断返回错误

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:])

这是全班给我的正确答案：

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.

标签： pythonbisection

Answer 1

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

您的代码没有正确处理“空字符串”的情况。对于长度为 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

相反，正确答案只是测试aStr == char长度为 1 的情况是否为真；我会坚持这一点，或者至少替换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'你想在后半部分找到它。

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

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