¿Cuál es la diferencia entre encontrar el medio de dos maneras diferentes en lo siguiente?
Para un algoritmo de divide y conquista en una matriz, necesitamos poder encontrar el elemento central de un rango. La forma obvia de hacerlo es mid = (leftSide + rightSide) / 2. Sin embargo, he oído que esa forma no es correcta y que necesitamos escribir mid = leftSide + (rightSide - leftSide) / 2 en su lugar. ¿Alguien puede explicar la diferencia entre esos dos?
davy.ai
La diferencia entre
mid = (leftSide + rightSide) / 2ymid = leftSide + (rightSide - leftSide) / 2está en cómo manejan la división de enteros.En el primer enfoque
mid = (leftSide + rightSide) / 2, agregamos los índices de los dos extremos y dividimos por 2 para obtener el índice medio. Sin embargo, este enfoque puede provocar desbordamiento de enteros sileftSide + rightSidees un valor grande y puede no funcionar como se espera.En el segundo enfoque
mid = leftSide + (rightSide - leftSide) / 2, primero encontramos la distancia entre los dos índices restandoleftSidederightSide. Esto nos da la longitud del rango que estamos dividiendo. Luego, dividimos esta distancia por 2 y la agregamos aleftSidepara obtener el índice medio.Este enfoque asegura que no estamos sumando dos enteros grandes que puedan provocar un desbordamiento y también maneja intervalos de longitud impar redondeando siempre hacia el índice inferior.
Por lo tanto, el segundo enfoque es una forma más sólida de encontrar el índice medio en un rango de un arreglo.