Error de recursión de búsqueda binaria: se excedió la profundidad máxima de recursión en la comparación.
Estaba tratando de ejecutar el programa Binary Search en Python. Seguí los pasos del algoritmo, pero me da este error. Aquí está mi código:
def binarySearch(a, k, l, r):
if l > r:
return -1
else:
mid = (l + (r - l)) // 2
if(a[mid] > k):
return binarySearch(a, k, l, mid - 1)
elif(a[mid] < k):
return binarySearch(a, k, mid + 1, r)
else:
return mid
t = int(input("Ingrese el número de casos de prueba: "))
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().rstrip().split()))
print(binarySearch(a, k, 0, n))
Error:
return binarySearch(a, k, mid + 1, r)
Archivo "e:/Coding/Algorithms/Searching/binarySearch.py", línea 10, en binarySearch
return binarySearch(a, k, mid + 1, r)
Archivo "e:/Coding/Algorithms/Searching/binarySearch.py", línea 10, en binarySearch
return binarySearch(a, k, mid + 1, r) [Línea anterior repetida 994 veces más]
Archivo "e:/Coding/Algorithms/Searching/binarySearch.py", línea 3, en binarySearch if r < l:
RecursionError: superado el límite máximo de recursión en comparación
davy.ai
El mensaje de error “RecursionError: la profundidad máxima de recursión se excedió en la comparación” sugiere que la función binarySearch está llamándose a sí misma recursivamente demasiadas veces y ha excedido el límite máximo de profundidad de recursión. Esto probablemente se debe a un bucle infinito.
Al observar el código, la línea que está causando el problema es la llamada recursiva a binarySearch en el bloque elif:
Parece que la condición para comprobar si el elemento en el índice medio es mayor que la clave de búsqueda no es correcta. La condición correcta debería ser:
De manera similar, la condición para comprobar si el elemento en el índice medio es menor que la clave de búsqueda debería ser:
Tenga en cuenta que estas condiciones utilizan los operadores menor que y mayor que en lugar de los operadores mayor que y menor que que se utilizaron en el código original. Esto se debe a que la clave de búsqueda siempre es menor que el elemento en el índice correcto y mayor que el elemento en el índice izquierdo. Por lo tanto, debemos comprobar si el elemento en el índice medio es mayor que o menor que la clave de búsqueda para saber dónde continuar la búsqueda.
Realizar estos cambios debería solucionar el RecursionError y permitir que el programa de búsqueda binaria se ejecute correctamente.