Bucle infinito en el algoritmo de búsqueda binaria.
Soy un traductor de español que traduce documentos de TI. Traduzca lo siguiente al español. No traduzca el código y la salida en markdown.
Soy un novato en algoritmos. Recientemente he comenzado a estudiar la búsqueda binaria e intenté implementarla por mi cuenta. La tarea es simple: tenemos una matriz de enteros “a” y un entero “x”. Si “a” contiene “x”, el resultado debería ser su índice; de lo contrario, la función debería devolver “-1”.
Aquí está el código que he escrito:
(definición de Python)
def binary_search(a, x):
l = 0
r = len(a)
while r – l > 0:
m = (l + r) // 2
if a[m] < x:
l = m
else:
r = m
if a[l] == x:
return l
return -1
Pero este código se queda en ciclo infinito en “a = [1, 2]” y “x = 2”. Supongo que tengo una condición de ciclo incorrecta (probablemente debería ser “r – l >= 0”), pero esta solución no ayuda. ¿Dónde estoy equivocado?
davy.ai
Hay un par de problemas en tu implementación del algoritmo de búsqueda binaria.
En primer lugar, el valor inicial de “r” debería ser establecido en “len(a) – 1” en lugar de “len(a)”, ya que el índice del último elemento en el arreglo es “len(a) – 1”.
En segundo lugar, en la línea “if a[m] < x:”, deberías actualizar “r” a “m – 1” en lugar de “m”, ya que ya has comparado el elemento medio con “x” y lo has encontrado menor que “x”. Del mismo modo, en el bloque “else”, deberías actualizar “l” a “m + 1” en lugar de “m”, ya que ya has comparado el elemento medio con “x” y lo has encontrado mayor o igual a “x”.
Con estos cambios, tu implementación debería verse así:
Ten en cuenta que también agregamos una verificación para asegurarnos de que el índice “l” esté dentro de los límites del arreglo “a” antes de devolver su valor. Esto se debe a que si el elemento no se encuentra en el arreglo, el valor final de “l” puede estar fuera de los límites del arreglo, lo que lleva a un “IndexError”.