Борьба с рекурсивным кодом для деления пополам поиска строки - PullRequest
Новая
       10

Борьба с рекурсивным кодом для деления пополам поиска строки

0 голосов
/ 16 февраля 2019

Итак, я беру урок по питону онлайн.Я хотел бы помочь определить различия между моим кодом и правильным кодом ответа.Я не комментировал свои, но ответ аннотирован, и все, что вам нужно, должно быть там, чтобы понять, что я пытаюсь сделать.Сначала я написал свой ответ самостоятельно, и оказалось, что он очень похож на правильный код ответа, данный классом.Однако мой код продолжает возвращать ошибку 

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.

1 Ответ

0 голосов
/ 16 февраля 2019

В вашей версии 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) имеет значение true, и не имеет значения, для чего установлено значение char.Так что aStr = 'z'; char = 'a' , will produce True` из вашей функции, что явно не правильно: 

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

Вместо этого правильный ответ просто проверяет, является ли aStr == char истинным для длины-is-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:])
...