Puedes llegar a la mitad usando ambos
bajo + (alto – bajo) / 2
y
- ¿Cuál es el mejor algoritmo para encontrar la ruta más corta en un gráfico orientado, donde algunos bordes están bloqueados y las teclas están en algún lugar de los nodos?
- ¿Por qué está completo el problema de la mochila NP incluso cuando tiene complejidad O (nW)?
- ¿Cómo funciona el algoritmo de armonía?
- ¿Cómo funciona el bucle dentro de un DP recursivo?
- ¿Cuál es la diferencia entre: d-ary, k-ary, n-ary, m-ary?
(bajo + alto) / 2
Si lo resuelven matemáticamente, dos cosas son iguales entre sí. Cuando la gente de ciencia no se da cuenta de que el número en la computadora está limitado por la CPU. En una computadora de 64 bits, el número más alto que puede obtener es 18,446,744,073,709,551,616. Entonces, si el número es mayor que ese número, se desborda.
Digamos
(bajo + alto) / 2 -> Versión 1
bajo + (alto – bajo) / 2 -> Versión 2
En la versión 1, está agregando más de lo que necesita. Piénselo de esta manera, digamos que tiene dos cuerdas, y está logrando la mitad de ellas al unir dos cuerdas juntas y luego cortarlas después de eso, lo que aún es correcto. Pero, si hace esto en la computadora, y si el número es demasiado grande, se desbordará como dije antes. Dependiendo de la implementación, puede obtener resultados diferentes (algunos pueden obtener un número negativo, otros pueden obtener un número máximo). Por ejemplo en Java,
int bajo = 1170105034
int high = 1347855270
(bajo + alto) / 2 // salidas -888503496
bajo + (alto – bajo) / 2 // salidas 1258980152
Pero lo que realmente tiene que hacer es saber cuánto más se va a comparar la media a baja, en este caso es (alta – baja) / 2 más, lo que da como resultado la versión 2. Pero, de nuevo, todavía puede obtener un desbordamiento en la versión 2, pero es mejor que la versión 1 porque es más probable que la versión 1 se desborde aunque la versión 2 no lo haga en algunos casos de gran número.
