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

Question

As mentioned in the title, I got 'None's when I run this piece of code.

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')

I have checked it for a few times, and I think it might happen in the process when judging aStr is equal to char or not, but I don't know how to correct it, or how it happens. Thanks in advance for anyone reading this thread!

For more information:

I use canopy python-2.7, and when I used 'run the current file' button, it returned None, but when I used 'run the selected text' button, it returned True. How could this happen?

Answer 1

You have two bugs in your tests.

You are testing against the whole list, containing one element, here:

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

aStr may be set to ['n'] and it'll still not be equal to 'n'. Use indexing:

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

Next, you are testing against the list again here:

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

That branch tests against the aStr list, not against char. Python 2 allows this kind of comparison, but will sort the types by type name in this case. str is always going to be greater than list, so that branch is always true.

Test against char instead:

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

Still, even with these errors corrected, you actually still manage to return True for the given sample:

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

because the n character happens to be located exactly at the first midpoint you test.