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

Hootenanny

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)

Androsphinx

Thanks for the comment. I noticed a weird when I run my code. It now returns True for character b,c,d in string 'abcd', but not a. – Hootenanny

Also, I wanted to make sure this is in fact a recursion, as the checker says it is not make a recursive call. – Hootenanny

You can test it by putting a print statement at the very begin of the function. If you see more than 1 "output" it means your method is being called recursively. – Androsphinx

@user3171116: Did you by chance put the check for char == m after aStr == '' or len(aStr) == 1? Because in that case, with even-length strings, it will fail to find the first character. (If you can't understand why, try running your code in an interactive visualizer, or adding print statements to show its progress.) But if you do it in the order Christian did, it should work. – Bulb

This is what I assume recursive calling looks like: <function isIn at 0x0000000002212B38> <function isIn at 0x0000000002212B38> <function isIn at 0x0000000002212B38> True – Hootenanny

@user3171116: Yes, this is what recursive calling looks like. You have at least one base case (for the empty string), and every non base case calls the same function with a smaller argument. And your print statements verify that it's calling itself twice. – Bulb

@user3171116: Wait a second… your code defines a function named isitIn, but your printouts show isIn. Are you by any chance mixing these up, where isitIn calls isIn (which then recursively calls itself… but isitIn itself never does any recursion)? – Bulb

Wow, you guys are great. I must say, no wonder stack overflow has been called the 'universal debugging tool'. That was the problem with the 'a'. What a great tool that is. Thx everybody! – Hootenanny

Oddly enough I get string out of range error for test case 'a', '' – Hootenanny

I will post the code I've tried, maybe there is a difference. See edit. – Androsphinx

Yeah, your code gets the same as mine: The 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 – Hootenanny

What input are you using to test it?? – Androsphinx

See edit. I think I figured out the issue. You must check for empty string before you compute m. – Androsphinx

let us continue this discussion in chat – Androsphinx

Answer 2

Overall, your code looks pretty good. But I would take a closer look at your first if statement. In particular, you're checking to see if the char is equal to the middle char. What would you want to return if your character was equal to the middle character?

Also, you need to make sure that all paths can be reached by your algorithm. Under what conditions would True be returned by your function?

Fransen

Thanks for the insight. I can't believe I missed that. It is amazing what a simple perspective change can do. Thanks again. – Hootenanny

Answer 3

this also works. slightly shorter as well:

def isIn(char, aStr):
    if len(aStr)==0:
        return False
    elif len(aStr)==1:
        return char == aStr
    elif char == aStr[len(aStr)//2]:
        return True
    else:
        if char < aStr[len(aStr)//2]:
            return isIn(char, aStr[0:len(aStr)//2])
        elif char > aStr[len(aStr)//2]:
            return isIn(char, aStr[len(aStr)//2:]) 
    return isIn(char, aStr)

Livingstone

Answer 4

I think this code can work properly, just I sorted the string before checking for character 'm':

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

Alienor