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

Christian Tapia · Accepted Answer · 2014-01-14 06:01:58Z

6

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)

edited Jan 14, 2014 at 6:01

answered Jan 14, 2014 at 4:44

Christian Tapia

34.2k7 gold badges58 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

14 Comments

user3171116 Over a year ago

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.

user3171116 Over a year ago

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

Christian Tapia Over a year ago

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.

abarnert Over a year ago

@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.

user3171116 Over a year ago

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!

|

Madison May · Accepted Answer · 2014-01-14 04:46:28Z

5

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?

answered Jan 14, 2014 at 4:46

Madison May

2,7833 gold badges24 silver badges32 bronze badges

1 Comment

user3171116 Over a year ago

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

xmcp · Accepted Answer · 2017-02-02 08:07:40Z

2

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)

edited Feb 2, 2017 at 8:07

xmcp

3,8722 gold badges25 silver badges41 bronze badges

answered Feb 2, 2017 at 6:32

user7504382

211 bronze badge

Comments

Mukhtar Edris · Accepted Answer · 2017-01-22 20:32:20Z

0

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)

answered Jan 22, 2017 at 20:32

Mukhtar Edris

1

Collectives™ on Stack Overflow

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

4 Answers 4

14 Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

14 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related