Cálculo medio de la búsqueda binaria en Python
¿Por qué “mid = (high + low) // 2” en lugar de “mid = high // 2“?
No puedo entender completamente por qué usan mid = (high + low)//2. Si alguien puede desmitificar mi comprensión de esto, sería muy apreciado 🙂
# Función iterativa de búsqueda binaria
# Devuelve el índice de x en la matriz arr dada si está presente,
# de lo contrario devuelve -1
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# Si x es mayor, ignorar la mitad izquierda
if arr[mid] < x:
low = mid + 1
# Si x es menor, ignorar la mitad derecha
elif arr[mid] > x:
high = mid - 1
# significa que x está presente en la mitad
else:
return mid
# Si llegamos aquí, entonces el elemento no estaba presente
return -1
# Matriz de prueba
arr = [2, 3, 4, 10, 40]
x = 10
# Llamada a la función
result = binary_search(arr, x)
if result != -1:
print("El elemento está presente en el índice", str(result))
else:
print("El elemento no está presente en la matriz")
davy.ai
La razón por la que se utiliza mid = (high + low)//2 en lugar de mid = high//2 es para asegurarnos de obtener el índice del medio exacto del array que se está buscando. La fórmula mid = (high + low)//2 calcula el promedio de los índices high y low y redondea hacia abajo al entero más cercano. Esto nos proporciona el índice medio preciso para dividir el array en dos mitades para la búsqueda binaria. Si utilizamos mid = high//2 en su lugar, no obtendremos el índice del medio exacto si la longitud del array es un número impar, lo que puede dar lugar a resultados incorrectos en la búsqueda. Por lo tanto, el uso de mid = (high + low)//2 asegura que siempre obtendremos el índice medio correcto independientemente de la longitud del array que se está buscando.