python - 如何编写代码来判断一个字符是否在字符串中？

Question

在此 quiz它告诉我写一个代码来确保一个字符是否在一个按字母顺序排序的字符串中，它告诉我二分搜索以确定一个字符是否在一个字符串中，并告诉我写一个递归代码而不是使用“在”(因为我在...)

我的代码是这样的:

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

    returns: True if char is in aStr; False otherwise
    '''
    var = 0
    if char == '' and aStr == '':
        return True
    elif char == '' or aStr == '' :
        return False
    elif aStr[int((len(aStr))/2)] == char :
        return True
    elif aStr[int((len(aStr))/2)] < char :
        var = int((len(aStr))/2)
        return isIn(char , aStr[var:])
    elif aStr[int((len(aStr))/2)] > char :
        var = int((len(aStr))/2)
        return isIn(char , aStr[0 : var])

但是当我传递像 (char = 'o' aStr = 'efggnqu', or char = 'y' aStr = 'orstv',or char = 'y' aStr = 'aamotv') 这样的值时，它会给我一个错误像这样:

Traceback (most recent call last):
  File "submission.py", line 21, in isIn
    return isIn(char , aStr[0 : var])
  File "submission.py", line 18, in isIn
    return isIn(char , aStr[var:])
  File "submission.py"...OUTPUT TRUNCATED

解决方案是什么？

Answer 1

这是一个修复方法:

def isIn(char, aStr):
    var = len(aStr) // 2 #Pulled out for readability (and speed)
    if char == '' and aStr == '':
        return True
    elif char == '' or aStr == '' :
        return False
    elif aStr[var] == char:
        return True
    elif aStr[var] < char:
        return isIn(char, aStr[var + 1:])
    elif aStr[var] > char:
        return isIn(char, aStr[:var])

关键部分是倒数第三行的 +1。没有它，单个字符将被一遍又一遍地传递。 1//2 向下舍入为 0，"n"[0:] 又是 "n"。

示例输出:

>>> isIn("o", "efgnqu")
False
>>> isIn("y", "orstv")
False
>>> isIn("y", "aamotv")
False
>>>