Todos hemos escuchado sobre la búsqueda binaria . Al ser un algoritmo tan útil, se ha incluido en STL de C ++ y en Java SDK, por ejemplo.
Sin embargo, en la implementación del SDK de Java de la búsqueda binaria Arrays.binarySearch()
, hubo un pequeño error. Al calcular el medio, que se hizo de esta manera: Middle = (Left + Right) / 2;
la parte (Left + Right)
podría desbordarse para valores grandes.
Para evitar el desbordamiento, el medio se puede calcular utilizando este ‘truco’: Middle = Left + (Right - Left) / 2;
- ¿Cuál es la diferencia entre las técnicas de prueba de software y las estrategias de prueba de software?
- ¿Qué título obtendría un mejor trabajo en la industria tecnológica, un título en informática o ingeniería de software?
- Ontologías (ciencia de la información): ¿Cuál es el mejor algoritmo para determinar la relación de los temas en un foro o red en línea (por ejemplo, temas principales y secundarios en Quora, o "Habilidades relacionadas" en Linkedin Skills and Expertise)?
- Tecnología: ¿Qué implica "gráfico"?
- ¿Qué tan difícil es programar un software como Facebook?
Simple, pero efectivo!
EDITAR:
- Joshua Bloch es quien escribió la búsqueda binaria del JDK. Aquí está su publicación de blog sobre el error mencionado anteriormente: Blog de investigación: Extra, Extra
- El informe de error: JDK-5045582 (coll) binarySearch () falla para un tamaño superior a 1 << 30