python - saber - Usar un algoritmo de bisección recursivo para verificar si el carácter está en una cadena

codigo de anagrama en java

Question

Actualmente estoy haciendo el curso de programación en edx y mis instrucciones son las siguientes: Usando la idea de búsqueda de bisección, escribe un algoritmo recursivo que comprueba si un personaje está incluido dentro de una cadena, siempre que la cadena esté en orden alfabético. Mi código (python 2.7) está aquí:

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)

Mi explicación: primero empiezo por encontrar el personaje del medio de la cuerda. Si es igual al personaje, devuelve False. Si no es igual al carácter, continúa para verificar si el carácter es más bajo que el carácter del medio, y luego usa la función recursiva para crear las pilas y finalmente devolver un valor booleano de True. Ahora utilicé el índice -1 y 1, ya que no quiero incluir el personaje del medio.

En lugar de una solución, preferiría obtener sugerencias ya que todavía estoy tratando de resolverlo, pero una perspectiva diferente nunca duele. ¡Gracias!

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

En general, tu código se ve bastante bien. Pero echaría un vistazo más de cerca a tu primera declaración if. En particular, está comprobando para ver si el carácter es igual a la mitad del carácter. ¿Qué te gustaría devolver si tu personaje era igual al personaje del medio?

Además, debe asegurarse de que el algoritmo pueda llegar a todas las rutas. ¿Bajo qué condiciones True sería devuelto por su función?

Answer 2

La función nunca vuelve True . Creo que debería devolver True cuando char == m , por lo que podría eliminarlo de la if-clause (que devuelve False ) y ponerlo en otro if :

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

Además, estás llamando a un método que no está definido. Creo que querías llamar recursivamente a isitIn .

Después de comparar char < m y char > m , debe "bisectar" la cadena, por lo tanto, no return isitIn(char, aStr[:-1]) ni return isIn(char, aStr[1:]) , sino pase ( en la llamada recursiva) la "mitad" de la cadena.

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

Editar: Por si acaso, el código que probé es:

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)

Answer 3

Creo que este código puede funcionar correctamente, solo ordené la cadena antes de verificar el carácter ''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)

Answer 4

esto también funciona un poco más corto también:

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)