Cálculo del índice de punto medio en la búsqueda binaria

3 minutos de lectura

Entonces, la forma correcta de calcular mid en una búsqueda binaria es mid = low + ((high - low) / 2) para manejar los errores de desbordamiento.

Mi implementación usa variables de 64 bits sin firmar y nunca veo una situación en la que mis arreglos se vuelvan tan grandes como para causar un desbordamiento. ¿Todavía necesito usar la implementación anterior o puedo usar mid = (low + high) / 2

¿Cuál es la mejor práctica aquí?

  • @EdHeal Creo que estos resultan ser iguales algebraicamente e incluso teniendo en cuenta el redondeo.

    – templatetypedef

    13/01/2014 a las 20:55

  • @EdHeal Me disculpo si me estoy perdiendo algo, pero ¿no salen iguales en ambos casos?

    – templatetypedef

    13 de enero de 2014 a las 21:22

  • low + (high - low) / 2 tampoco se garantiza que sea seguro. Trabajo en código que admite índices negativos. Un positivo high y negativo low podría desbordarse high - low.

    –Eric Postpischil

    13 de enero de 2014 a las 21:43


Si no hay posibilidad de desbordamiento, la forma segura de desbordamiento de calcular el punto medio es técnicamente innecesaria: puede usar la fórmula insegura si lo desea. Sin embargo, probablemente sea una buena idea mantenerlo allí de todos modos, en caso de que su programa se modifique algún día para romper sus suposiciones. Creo que agregar una sola instrucción de CPU para hacer que su código esté preparado para el futuro es una gran inversión en la capacidad de mantenimiento de su código.

  • Además: nunca se sabe cuándo alguien va a cortar y pegar su código y usarlo en otro lugar, donde sus suposiciones no vuelan. Tal vez lo ejecuten en una máquina de 32 bits y usen matrices enormes, o algo así. Si conoce un lenguaje de programación que siempre funciona, no lo reemplace con uno que funcione ocasionalmente a menos que haya una buena razón. (Mejor que guardar algunas pulsaciones de teclas o 2 instrucciones de máquina en un bucle) solo mis $0.02

    – JVMATL

    13 de enero de 2014 a las 21:10

Avatar de usuario de Dabo
dabo

Revisa este artículo Casi todas las búsquedas binarias y Mergesorts están rotas

Mejores prácticas (por hoy)

Probablemente más rápido, y podría decirse que tan claro es: 6: int mid = (low + high) >>> 1;

y después de eso :

En C y C++ (donde no tiene el operador >>>), puede hacer esto: 6: mid = ((int sin firmar) bajo + (int sin firmar) alto)) >> 1;

Y al final :

Actualización del 17 de febrero de 2008: gracias a Antoine Trux, miembro principal del personal de ingeniería del Centro de investigación de Nokia en Finlandia, por señalar que no se garantizaba que la solución original propuesta para C y C++ (línea 6) funcionara según el estándar C99 pertinente (ESTÁNDAR INTERNACIONAL – ISO/IEC – 9899 – Segunda edición – 1999-12-01, 3.4.3.3), que dice que si suma dos cantidades con signo y obtiene un desbordamiento, el resultado es indefinido. El estándar C anterior, C89/90 y el estándar C++ son idénticos a C99 en este aspecto. Ahora que hemos hecho este cambio, sabemos que el programa es correcto;)

En pocas palabras, siempre habrá un caso en el que no funcionará

avatar de usuario del codificador
descifrador

El método de Don Knuth funciona perfectamente a través de una máscara de bits sin posibilidad de desbordamiento:

return (low & high) + ((low ^ high) >> 1)

EDITAR: low + high = (low ^ high) + (low & high) << 1

página 19, El arte de la programación informática, vol. 4, Donald E.Knuth

Entonces, la forma correcta de calcular mid en una búsqueda binaria es mid = low + ((high - low) / 2) para manejar los errores de desbordamiento.

Esto es incorrecto. Considerar low = 18 * pow(10, 18) y high = 1 * pow(10, 18). Ambas cosas mid = (low + high) / 2 y tu método se desborda, dando 276627963145224192 en lugar de lo correcto 9500000000000000000.

¿Ha sido útil esta solución?