Using a recursive bisection algorithm to check if character is in string

Question

I am currently doing the programming course over at edx and my instructions are as follows: Using the idea of bisection search, write a recursive algorithm that checks if a character is included within a string, as long as the string is in alphabetical order. My code(python 2.7) is here:

def isitIn(char, aStr):
   m = aStr[len(aStr) // 2]
   if aStr == '' or len(aStr) == 1 or char == m:
      return False
   else:
      if char < m:
         return isitIn(char, aStr[:-1])
      elif char > m:
         return isitIn(char, aStr[1:])
   return isitIn(char, aStr)

My explanation: I first start by finding the middle character of the string. If it equals the character, it returns False. If it does not equal the character, it goes on to check whether the character is lower than the middle character, and then using the recursive function to create the stacks and ultimately return a boolean value of True. Now I used the -1 and 1 index, as I do not want to include the middle character.

Instead of a solution, I would rather get hints as I am still trying to figure it out, but a different perspective never hurts. Thanks!

Error message:
Test: isIn('a', '')
Your output:
Traceback (most recent call last):
File "submission.py", line 10, in isIn
m = aStr[len(aStr) // 2]
IndexError: string index out of range
Correct output:
False

Answer 1

The function is never returning True. I think it should return True when char == m, so you could delete it from the if-clause(that is returning False) and put it in another if:

if char == m:
   return True
elif aStr == '' or len(aStr) == 1:
    return False
else:
    ...

Also, you are calling isIn method which is not defined. I think you wanted to recursively call isitIn.

After comparing char < m and char > m you should "bisect" the string, so don't do return isitIn(char, aStr[:-1]) nor return isIn(char, aStr[1:]), instead pass (in the recursive call) the "half" of the string.

if char < m:
    return isitIn(char, aStr[:len(aStr) // 2])
elif char > m:
    return isitIn(char, aStr[len(aStr) // 2:])

Edit: Just in case, the code I've tried is:

def isitIn(char, aStr):
    if aStr == '':  # Check for empty string
        return False
    m = aStr[len(aStr) // 2]
    if char == m:
       return True
    elif len(aStr) == 1:
        return False
    else:
       if char < m:
           return isitIn(char, aStr[:len(aStr) // 2])
       elif char > m:
           return isitIn(char, aStr[len(aStr) // 2:])
    return isitIn(char, aStr)