Un problema en muchas implementaciones de búsqueda binaria

Considere la siguiente implementación en C de la función de búsqueda binaria , ¿hay algo malo en esto?

// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r)
    {
        // find index of middle element
        int m = (l+r)/2;
  
        // Check if x is present at mid
        if (arr[m] == x) return m;
  
        // If x greater, ignore left half
        if (arr[m] < x) l = m + 1;
  
        // If x is smaller, ignore right half
        else r = m - 1;
    }
  
    // if we reach here, then element was not present
    return -1;
}

Lo anterior se ve bien excepto por una cosa sutil, la expresión “m = (l+r)/2”. Falla para valores grandes de l y r. Específicamente, falla si la suma de alto y bajo es mayor que el valor int positivo máximo (2 ³¹ – 1). La suma se desborda a un valor negativo y el valor permanece negativo cuando se divide por dos. En C, esto provoca un índice de array fuera de los límites con resultados impredecibles.

¿Cuál es la manera de resolver este problema?
La siguiente es una forma:

        int mid = low + ((high - low) / 2); 

Probablemente más rápido, y podría decirse que tan claro es (funciona solo en Java, consulte esto ):

        int mid = (low + high) >>> 1; 

En C y C++ (donde no tiene el operador >>>), puede hacer esto:

        mid = ((unsigned int)low + (unsigned int)high)) >> 1 

El problema similar también aparece en Merge Sort .

El contenido anterior está tomado del blog de investigación de Google .

Consulte esto también, señala que las soluciones anteriores pueden no funcionar siempre.

El problema anterior ocurre cuando la longitud de la array es 2 ³⁰ o mayor y la búsqueda se mueve repetidamente a la segunda mitad de la array. No es probable que este tamaño de array aparezca la mayor parte del tiempo. Por ejemplo, cuando probamos el siguiente programa con el compilador Code Blocks de 32 bits , obtenemos un error de compilación.

int main()
{
    int arr[1<<30];
    return 0;
}

Producción:

error: size of array 'arr' is too large

Incluso cuando probamos la array booleana, el programa se compila bien, pero falla cuando se ejecuta en Windows 7.0 y el compilador Code Blocks de 32 bits

#include <stdbool.h>
int main()
{
    bool arr[1<<30];
    return 0;
}

Salida: No hay error de compilación, pero falla en tiempo de ejecución.

Fuentes:
http://googleresearch.blogspot.in/2006/06/extra-extra-read-all-about-it-nearly.html
http://locklessinc.com/articles/binary_search/

Este artículo es una contribución de Abhay Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.