Geek Answers Handbook

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

I am currently working in edx programming, and my instructions are as follows: Using the idea of ​​searching in half, write a recursive algorithm that checks if a character is included in the string if 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: First, I start by looking for the middle character of the string. If it is equal to a character, it returns False. If it does not match the character, it continues to check whether the character is below the middle character, and then uses the recursive function to create stacks and ultimately returns the logical value True. Now I used the index -1 and 1, since I do not want to include the middle character.

, , . !

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
+4
4

True. , True char == m, if-clause ( False) if:

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

, isIn, . , isitIn.

char < m char > m "" , return isitIn(char, aStr[:-1]) return isIn(char, aStr[1:]), ( ) ".

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

: , , :

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)
+5

, . . , , char char. , ?

, , . True ?

+5

. :

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)
+1

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

More articles:


All Articles