algorithm - pseint - ¿Cuáles son los peligros de implementar una búsqueda binaria?

busqueda binaria pseint

Question

La búsqueda binaria es más difícil de implementar de lo que parece. "Aunque la idea básica de la búsqueda binaria es comparativamente sencilla, los detalles pueden ser sorprendentemente difíciles ..." - Donald Knuth.

¿Qué errores es más probable que se introduzcan en una nueva implementación de búsqueda binaria?

Answer 1

Aquí hay algunos que puedo pensar:

• Errores uno a uno , al determinar el límite del siguiente intervalo
• Manejo de elementos duplicados , si se supone que debe devolver el primer elemento igual en el conjunto, pero en su lugar devolvió un elemento igual posterior
• Desbordamientos / desbordamientos numéricos al calcular índices, con matrices enormes
• Implementación recursiva vs no recursiva , una elección de diseño que debes considerar

¿Es esto lo que tienes en mente?

Answer 2

No tener en cuenta que al calcular el punto medio entre dos índices que suman los valores alto y bajo puede provocar un desbordamiento de entero.

Referencia

Answer 3

Si tiene cerca el libro Programming Pearls, debe verificar el capítulo 4.

edit2: Como se señaló en los comentarios, puede descargar el borrador del capítulo I que mencionó el sitio web del autor: http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html

Answer 4

Lee esto La implementación de búsqueda binaria de Java ocultó un error durante casi una década antes de que nadie lo encontrara.

El error es un desbordamiento de enteros. No causó problemas a las personas porque casi nadie estaba buscando estructuras de datos lo suficientemente grandes.

Answer 5

La arquitectura de canalización de los procesadores modernos es mucho más adecuada para realizar búsquedas lineales que para realizar búsquedas binarias que tienen muchas decisiones y ramas.

Por lo tanto, un error de rendimiento común y una optimización prematura (ya sabes, esta es la raíz de todo mal) está utilizando la búsqueda binaria en absoluto cuando una búsqueda lineal simple sería más rápida y, por supuesto, más simple.

Dependiendo de la cantidad de lecturas, incluso ordenar los datos puede hacer que todo sea más lento. Un punto de equilibrio entre lineal y binario puede ser fácilmente de 1000 elementos para claves simples (por ejemplo, enteros de 32 bits).

Answer 6

Una razón crucial por la cual las personas no pueden implementar la búsqueda binaria correctamente es que no caracterizamos bien la búsqueda binaria, es un problema bien definido, pero generalmente uno no lo define bien.

Una regla universal es aprender del fracaso. Aquí, pensar en casos "inválidos" ayuda a aclarar el problema. ¿Qué pasa si la entrada está vacía? ¿Qué pasa si la entrada contiene duplicados? ¿Debería implementarlo mediante una prueba condicional o dos pruebas (más una prueba adicional para la terminación anticipada) por iteración? y otros problemas técnicos, como desbordamiento / subdesbordamiento numérico en índices informáticos y otros trucos.

Los errores que podrían evitarse caracterizan bien el problema son los errores uno a uno y el manejo de elementos duplicados, como señaló @Zach Scrivena.

Muchas personas ven la búsqueda binaria como encontrar un valor objetivo dada una matriz ordenada. Así es como se usa el binario, no la búsqueda binaria per se.

Trataré de dar una definición / formulación relativamente rigurosa de la búsqueda binaria, y mostraré una forma de evitar los errores uno por uno y los problemas duplicados, adaptándome a un enfoque específico, que, por supuesto, no es nuevo.

# (my) definition of binary search:
input: 
    L: a ''partially sorted'' array, 
    key: a function, take item in L as argument
prerequisite: 
    by ''partially sorted'' I mean, if apply key function to all item of L, we get a 
    new array of bool, L_1, such that it can''t be partitioned to two left, right blocks, 
    with all item in left being false, all item in right being true. 
    (left or/and right could be empty)
output: 
    the index of first item in right block of L_1 (as defined in prerequisite). 
    or equivalently, the index of first item in L such that key(item) == True

esta definición resuelve naturalmente el problema duplicado.

Comúnmente hay dos formas de denotar arreglos, [] y [), prefiero el último, una equivalencia de [) enfoque es usar el par (inicio, conteo) en su lugar.

# Algorithm: binary search
# input: L: a ''partially sorted'' array, key: a function, take item in L as argument
    while L is not empty:
        mid = left + (right - left)/2  # or mid = left + count/2
        if key(mid item) is True:
            recede right # if True, recede right
        else:
            forward left # if False, forward left
    return left

Por lo tanto, si hace su parte "if True, Recede (end)" y "if False, Forward (start)" a la derecha, ya casi ha terminado. Lo llamo la "regla FFTR" de la búsqueda binaria. Si va a encontrar el primer artículo, como en la definición anterior, se iniciará el de la izquierda, sin embargo, se iniciará el derecho si va a encontrar el último elemento. Te ajustas a la moda [), luego un posible implemento es,

while left<right:
    mid = left + (right - left)/2
    if key(L(mid)) == True:
        right = mid
    else:
        left = mid+1
    return left

validemos aún más, primero demostremos la convergencia y luego mostremos la corrección.

convergencia:

whenever left == right, we exit loop (also true if being empty at the first)

so, in the loop, if denote, 

    diff = (right - left)/2, 

    lfstep = 1 + diff/2, ''lfstep'' for ''left index forward step size''

    rbstep = diff - diff/2, ''rbstep'' for ''right index back (recede) step size''

it can be show that lfstep and rbstep are alway positive, so left and right 
will be equal at last. 

both lfstep and rbstep are asymptotically half of current subarray size, so it''s 
of logarithm time complexity.

exactitud:

if the input array is empty:
    return the left index;
else:
    if key(mid item) is true:
        "recede right"
        so mid and all item after mid are all true, we can reduce the search range 
        to [left, mid), to validate it, there are two possible cases,
        case 1:
            mid is the first item such that key(item) is True, so there are no true items 
            in new search range [left, mid), so the test will always be false, and we 
            forward left at each iteration until search range is empty, that is  
            [finalleft,mid), since we return finalleft, and finalleft == mid, correctly done!
        case 2:
            there are item before mid such that key(item) is True,
            in this case we just reduce to a new problem of smaller size
    else:
        "forward left"
        mid and all item before mid is false, since we are to find the first true one, 
        we can safely reduce to new search range [mid+1, right) without change the result.

equivalente (inicio, conteo) versión,

while count>0:
    mid = start + count/2
    if key(L[mid]) == True:
        right = mid
    else:
        left = mid+1
return left

para resumir , si se ajusta a la convención [),

1. define your key function of your problem, 
2. implement your binary search with "FFTR rule" -- 
    "recede (end) if True ( key(item) == True) else forward (start)" 
    examples:
        if to find a value target, return index or -1 if not found,
        key = lambda x: x>=target, 
        if L[found_index] == target: return found_index
        else: return -1

En cuanto a la terminación anticipada con una prueba adicional, no creo que valga la pena pagar, pero puedes intentarlo.

Answer 7

Esta pregunta recién se hizo nuevamente . Además de la cita de Knuth que "Aunque la idea básica de la búsqueda binaria es comparativamente sencilla, los detalles pueden ser sorprendentemente complicados", existe el asombroso hecho histórico (ver TAOCP, Volumen 3, sección 6.2.1) que la búsqueda binaria se publicó por primera vez en 1946 pero la primera búsqueda binaria publicada sin errores fue en 1962. Y está la experiencia de Bentley de que cuando asignó búsqueda binaria en cursos para programadores profesionales en lugares como Bell Labs e IBM y les dio dos horas, todos informaron que lo habían hecho bien, y al examinar su código, el 90% de ellos tenían errores, año tras año.

Quizás la razón principal por la que tantos programadores cometen errores con la búsqueda binaria, además de la Ley de Sturgeon, es que no son lo suficientemente cuidadosos: Programming Pearls lo cita como "escriba su código, arrójelo a la pared y tenga un control de calidad o prueba". con el enfoque de los errores ". Y hay muchas posibilidades de error. No solo el error de desbordamiento que mencionan varias de las otras respuestas aquí, sino errores lógicos.

A continuación se muestran algunos ejemplos de errores de búsqueda binaria. Esto de ninguna manera es exhaustivo. (Como escribe Tolstoy en Anna Karenina : "Todas las familias felices son iguales, cada familia infeliz es infeliz a su manera", cada programa de búsqueda binario incorrecto es incorrecto a su manera).

Pattis

El siguiente código de Pascal está tomado de los errores de Libro de texto en la búsqueda binaria (1988) de Richard E Pattis. Miró veinte libros de texto y se le ocurrió esta búsqueda binaria (por cierto, Pascal usa índices de matriz a partir de 1):

PROCEDURE BinarySearch (A         : anArray,
                        Size      : anArraySize,
                        Key       : INTEGER,
                        VAR Found : BOOLEAN;
                        VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN         
   LOW := 1;
   High := Size;

   REPEAT
      Index := (Low + High) DIV 2;
      If Key < A[Index]
         THEN High := Index - 1
         ELSE Low  := Index + 1
   UNTIL (Low > High) OR (Key = A[Index]);

   FOUND := (Low <= High)
END;

¿Se ve bien? Esto tiene más de un error. Antes de seguir leyendo, mira si puedes encontrarlos todos. Debería poder adivinar lo que hace el código incluso si está viendo Pascal por primera vez.

Describe cinco errores que tienen muchos programas, y en particular lo anterior tiene:

Error 1 : No se ejecuta en el tiempo O (log n), donde n = Tamaño. En su entusiasmo por la práctica de programación adecuada, algunos programadores escriben la búsqueda binaria como una función / procedimiento, y le pasan una matriz. (Esto no es específico de Pascal, imagine en C ++ que pasa un vector por valor en lugar de por referencia). Este es Θ (n) tiempo para pasar la matriz al procedimiento, lo cual frustra el propósito total. Peor aún, algunos autores aparentemente dan una búsqueda binaria recursiva , que pasa una matriz cada vez, dando un tiempo de ejecución que es Θ (n log n). (Esto no es exagerado, de hecho he visto código como este).

Error 2 : falla cuando tamaño = 0. Esto puede estar bien. Pero dependiendo de la aplicación prevista, la lista / tabla que se busca puede reducirse a 0, y debe manejarse en alguna parte.

Error 3 : Da una respuesta incorrecta. Siempre que la iteración final del bucle comience con Low = High (por ejemplo, cuando Size = 1), establece Found: = False, incluso si Key está en la matriz.

Error 4 : Causa un error cuando Key es menor que el elemento más pequeño de la matriz. (Después de que Index convierte en 1, establece High en 0, etc., provoca un error fuera de límites).

Error 5 : Causa un error cada vez que Key es mayor que el elemento más grande de la matriz. (Después de que Index convierte en Size , establece Low to Size + 1, etc., provoca un error fuera de límites).

También señala que algunas formas obvias de "corregir" estos errores también resultan ser incorrectas. El código de la vida real también suele tener esta propiedad, cuando un programador escribió algo incorrecto, encontró un error y luego lo "arregló" hasta que pareció correcto sin pensarlo lo suficiente.

De los 20 libros de texto que probó, solo 5 tenían una búsqueda binaria correcta. En los 15 restantes (dice irónicamente, 16), encontró 11 instancias del Error 1, seis instancias del Error 2, dos de cada uno de los Errores 3 y 4, y uno del Error 5. Estos números suman mucho más que 15, porque varios de ellos tenían múltiples errores.

Más ejemplos

La búsqueda binaria se utiliza para algo más que buscar una matriz para ver si contiene un valor, por lo que aquí hay un ejemplo más por el momento. Puedo actualizar esta lista cuando pienso en más.

Supongamos que tiene una función creciente (no decreciente) f: R-> R, y (porque quiere una raíz de f, por ejemplo), quiere encontrar la t más grande tal que f(t) < 0 . Vea cuántos errores puede encontrar en lo siguiente:

float high = INF, low = 0;
while(high != low) {
   float mid = (low + high)/2;
   if(f(mid)>0) high=mid;
   else low=mid;
}
printf("%f", high);

(Algunos: puede que no haya tal t en [0, INF], si f es 0 en un intervalo, entonces esto es incorrecto, nunca compare los números de punto flotante para la igualdad, etc.)

Cómo escribir una búsqueda binaria

Solía ​​cometer varios de esos errores: las primeras docenas de veces que escribí búsqueda binaria (que fue durante concursos de programación con presión de tiempo), aproximadamente el 30% de las veces había un error en alguna parte, hasta que encontré la manera más sencilla de escribirlo correctamente. No tengo una búsqueda binaria incorrecta desde (como recuerdo). El truco es muy simple:

Mantener un invariante.

Encuentre / decida y explicite alguna propiedad invariable que sus variables "baja" y "alta" satisfagan a lo largo del ciclo: antes, durante y después. Asegúrate de que nunca sea violado. Por supuesto, también debe pensar en la condición de terminación. Esto se explica detalladamente en el Capítulo 4 de Programming Pearls, que deriva un programa de búsqueda binario de métodos semi-formales.

Por ejemplo, para abstraer un poco la condición que se está examinando, supongamos que desea encontrar el mayor valor entero x para el cual alguna condición posible poss(x) es verdadera. Incluso esta definición explícita de problema es más de lo que muchos programadores comienzan. (Por ejemplo, poss(x) puede ser a[x] ≤ v para algún valor v ; esto es para averiguar cuántos elementos en la matriz ordenada a son más que v , por ejemplo). Entonces, una forma de escribir una búsqueda binaria es:

int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
    int mid = lo + (hi-lo)/2;
    if(poss(mid)) lo = mid;
    else hi = mid;
}
printf("%d /n",lo);

Puede agregar más afirmaciones y otras comprobaciones, pero la idea básica es que, debido a que actualiza lo a mid solo cuando sabe que poss(mid) es verdadero, mantiene el invariante que poss(lo) siempre es verdadero. De forma similar, estableces hi a mid solo cuando poss(mid) es falsa, por lo que mantienes invariante que poss(hi) siempre es falso. Piense en la condición de terminación por separado. (Tenga en cuenta que cuando hi-lo es 1, mid es lo mismo que lo . Así que no escriba el ciclo como while(hi>lo) , o tendrá un ciclo infinito.) Al final del ciclo, se garantiza que hi-lo es como máximo 1, y como tu siempre mantienes tu invariante ( poss(lo) es verdadero y poss(hi) es falso), no puede ser 0. Además, de nuevo debido a tu invariante, sabes ese es el valor para devolver / imprimir / usar. Hay otras maneras de escribir búsquedas binarias, por supuesto, pero mantener un invariante es un truco / disciplina que siempre ayuda.