Skip to the content ForoHackers
Log inJoin

Búsqueda binaria con el diccionario, y el fallo de `(lo + hi) / 2`

AlgorithmsCompetitive programmingData structures
#1014 · SiestaDeAlgoritmos · · Report

La búsqueda binaria es como buscar una palabra en un diccionario de papel: no empiezas por la A, abres por la mitad. Si la palabra que buscas va antes, te quedas con la primera mitad; si va después, con la segunda. Repites. Con mil palabras, diez aperturas. Con mil millones, treinta.

int busca(const int *v, int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int medio = lo + (hi - lo) / 2;
        if (v[medio] == x) return medio;
        if (v[medio] < x)  lo = medio + 1;
        else               hi = medio - 1;
    }
    return -1;
}

Fíjate en la línea del medio. Lo natural es (lo + hi) / 2, pero si lo y hi son grandes (arrays de más de mil millones de elementos con int de 32 bits), la suma se pasa del máximo y se desborda. Con enteros con signo, eso es comportamiento indefinido en C. lo + (hi - lo) / 2 nunca se sale, porque hi - lo es siempre positivo y pequeño.

Es un fallo que estuvo en bibliotecas muy usadas durante años, porque los arrays eran más pequeños de lo necesario para notarlo. Hasta que dejaron de serlo.

Dos condiciones para que funcione: el array tiene que estar ordenado, y los límites se actualizan con medio + 1 y medio - 1. Si pones lo = medio, tienes un bucle infinito esperando.

#1436 · ElDelPuntoYComa · · Report

Exacto: el desbordamiento de int con signo es comportamiento indefinido, no solo "da la vuelta". Un compilador puede asumir que no ocurre y optimizar en consecuencia. Con size_t y sin signo sí está definido, pero entonces hi = medio - 1 puede salirse por abajo cuando medio vale 0. Cada tipo tiene su trampa.

#1437 · PacoElDelCronjob · · Report

Buen hilo para alguien que empieza. Lo del diccionario lo explica mejor que mis apuntes de la carrera.

#1438 · SiestaDeAlgoritmos · · Report

Gracias, Punto y Coma: no había pensado en el caso del size_t y el cero. Lo añado a mis apuntes. Y gracias, Paco.

#1439 · off_by_two · · Report

(In English, sorry.) Related puzzle: given a monotone predicate (false, false, ..., true), find the first true with binary search. Same idea applied to answers instead of positions, and half of all contest problems.

#1440 · LaAbuelaDelCOBOL · · Report

En COBOL hacíamos esto con SEARCH ALL sobre tablas ordenadas. Misma idea, y el mismo cuidado con que la tabla estuviera de verdad ordenada, que no siempre lo estaba.

Log in or join to reply.