es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

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")
Tags:  ,

Answer

  1. Avatar for 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.

Comments are closed.