在进行二分搜索确定单个字符是否在 alphabetical-ordered 字符串中时得到 'None'

Question

正如标题所说，我运行这段代码时得到了'None。

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

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

isIn('n', 'abfnuv')

我查了好几遍，我觉得可能是在判断aStr是否等于char的过程中出现的，但是不知道怎么改正，也不知道是怎么出现的。预先感谢任何阅读此主题的人！

更多信息：

我用的是canopy python-2.7，当我用'run the current file'按钮的时候，返回的是None，但是当我用的是'run the selected text'按钮的时候，它返回的是True。怎么会这样？

Answer 1

你的测试有两个错误。

您正在测试整个列表，其中包含一个元素，此处：

elif len(aStr)==1:
    return aStr==char

aStr 可能设置为 ['n']，但它仍然不等于 'n'。使用索引：

elif len(aStr)==1:
    return aStr[0]==char

接下来，您将在此处再次对列表进行测试：

elif aStr[(len(aStr)/2)]<aStr:

该分支针对 aStr 列表进行测试，而不是针对 char。 Python 2 允许这种比较，但在这种情况下将按类型名称对类型进行排序。 str 总是会大于 list，因此分支总是为真。

改为 char 测试：

elif aStr[(len(aStr)/2)]<char:

尽管如此，即使纠正了这些错误，您实际上仍然设法 return True 对于给定的样本：

>>> isIn('n', 'abfnuv')
True

因为 n 字符恰好位于您测试的第一个中点。

在进行二分搜索确定单个字符是否在 alphabetical-ordered 字符串中时得到 'None'

Got 'None's when doing a bisection search determining whether a single character is in an alphabetical-ordered string or not

python

string

python-2.7

recursion

bisection