Domanda Quali sono le insidie ​​nell'implementazione della ricerca binaria?


La ricerca binaria è più difficile da implementare di quanto sembri. "Sebbene l'idea di base della ricerca binaria sia relativamente semplice, i dettagli possono essere sorprendentemente complessi ..." - Donald Knuth.

È probabile che i bug vengano introdotti in una nuova implementazione di ricerca binaria?


44
2018-02-02 18:35


origine


risposte:


Ecco alcuni che mi viene in mente:

  • Errori off-by-one, quando si determina il limite dell'intervallo successivo
  • Gestione di oggetti duplicati, se si suppone di restituire il primo elemento uguale nell'array ma invece restituito un oggetto uguale successivo
  • Sottoutilizzazioni / overflow numerici quando si calcolano gli indici, con enormi matrici
  • Ricorsivo vs non ricorsiva implementazione, una scelta di design che dovresti prendere in considerazione

Sono questi che hai in mente?


26
2018-02-02 18:38



Questa domanda era ho appena chiesto di nuovo di recente. Oltre alla citazione di Knuth, "Sebbene l'idea di base della ricerca binaria sia relativamente semplice, i dettagli possono essere sorprendentemente complessi", c'è l'incredibile fatto storico (vedi TAOCP, Volume 3, sezione 6.2.1) che la ricerca binaria è stata pubblicata per la prima volta in 1946 ma la prima ricerca binaria pubblicata senza errori Era nel 1962. E c'è l'esperienza di Bentley che quando ha assegnato la ricerca binaria in corsi per programmatori professionisti in posti come Bell Labs e IBM e ha dato loro due ore, tutti hanno riferito di averlo fatto bene, e esaminando il loro codice il 90% di loro ha avuto insetti - anno dopo anno.

Forse la ragione fondamentale per cui così tanti programmatori commettono errori con la ricerca binaria, oltre alla legge di Sturgeon, è che non sono abbastanza attenti: Perle di programmazione cita questo come "scrivi il tuo codice, gettalo oltre il muro e applica l'approccio di Quality Assurance o Testing with the bugs". E c'è un sacco di possibilità di errore. Non solo l'errore di overflow che molte delle altre risposte qui menzionano, ma errori logici.

Di seguito sono riportati alcuni esempi di errori di ricerca binaria. Questo non è affatto esauriente. (Come scrive Tolstoy Anna Karenina - "Tutte le famiglie felici sono uguali, ogni famiglia infelice è infelice a modo suo" - ogni errato programma di ricerca binaria non è corretto a suo modo.)

Pattis

Il seguente codice Pascal è preso dalla carta Errori di testo nella ricerca binaria (1988) di Richard E Pattis. Ha esaminato venti libri di testo e ha trovato questa ricerca binaria (BTW, Pascal usa gli indici di matrice a partire da 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;

Sembra ok? Questo ha più di un errore. Prima di leggere ulteriormente, vedi se riesci a trovarli tutti. Dovresti essere in grado di indovinare cosa fa il codice anche se stai vedendo Pascal per la prima volta.


Descrive cinque errori che molti programmi hanno, e in particolare il precedente ha:

Errore 1: Non viene eseguito in O (log n) time, dove n = Size. Nel loro entusiasmo per la corretta programmazione, alcuni programmatori scrivono la ricerca binaria come una funzione / procedura e la passano in un array. (Questo non è specifico per Pascal, immagina in C ++ che passa un vettore per valore piuttosto che per riferimento.) Questo è Θ (n) tempo solo per passare l'array alla procedura, che sconfigge l'intero scopo. Ancora peggio, alcuni autori sembrano dare un ricorsivo ricerca binaria, che passa ogni volta un array, fornendo un tempo di esecuzione Θ (n log n). (Questo non è inverosimile, in realtà ho visto un codice come questo.)

Errore 2: Fallisce quando taglia = 0. Può essere ok. Ma a seconda dell'applicazione desiderata, la lista / tabella viene cercata potrebbe riduci a 0 e deve essere gestito da qualche parte.

Errore 3: Dà una risposta sbagliata. Ogni volta che l'iterazione finale del loop inizia con Low = High (ad esempio, quando Size = 1), imposta Found: = False, anche se Key è nella matrice.

Errore 4: Causa un errore ogni volta Key è inferiore all'elemento più piccolo dell'array. (Dopo Index diventa 1, imposta High a 0, ecc .; causa un errore out-of-bounds.)

Errore 5: Causa un errore ogni volta Key è maggiore dell'elemento più grande dell'array. (Dopo Index diventa Size, imposta Low alla taglia + 1 ecc .; causa un errore out-of-bounds.)

Egli sottolinea anche che alcuni ovvi modi per "correggere" questi errori risultano errati. Anche il codice della vita reale ha spesso questa proprietà, quando un programmatore ha scritto qualcosa di sbagliato, ha trovato un errore e poi lo ha "risolto" fino a quando sembrava correggi senza pensarci abbastanza attentamente.

Dei 20 libri di testo che ha provato, solo 5 avevano una ricerca binaria corretta. Nei restanti 15 (dice 16, ironicamente), ha trovato 11 casi di errore 1, sei casi di errore 2, due ciascuno di errori 3 e 4 e uno di errore 5. Questi numeri si sommano a molto più di 15, perché molti di loro avevano più errori.


Altri esempi

La ricerca binaria viene utilizzata per qualcosa di più della semplice ricerca di una matrice per vedere se contiene un valore, quindi ecco un altro esempio per ora. Potrei aggiornare questa lista come penso di più.

Supponiamo che tu abbia una funzione crescente (non decrescente) f: R-> R, e (perché vuoi una radice di f, per esempio), vuoi trovare il più grande t così f(t) < 0. Guarda quanti bug puoi trovare in quanto segue:

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);

(Alcuni: potrebbe non esserci t in [0, INF], se f è 0 su un intervallo, questo è sbagliato, non confrontare mai i numeri in virgola mobile per l'uguaglianza, ecc.)

Come scrivere la ricerca binaria

Ho usato molti di questi errori - le prime poche decine di volte che ho scritto la ricerca binaria (che era durante i contest di programmazione con la pressione del tempo), circa il 30% delle volte c'era un bug da qualche parte - fino a quando ho trovato il modo semplice per scriverlo correttamente. Da allora non ho una ricerca binaria sbagliata (come ricordo). Il trucco è molto semplice:

Mantenere invariato.

Trova / decidi e rendi esplicita una proprietà invariante che le tue variabili "basse" e "alte" soddisfano durante il ciclo: prima, durante e dopo. Assicurati che non venga mai violato. Ovviamente devi anche pensare alle condizioni di terminazione. Questo è spiegato in dettaglio nel capitolo 4 di Perle di programmazione quale deriva un programma di ricerca binario dai metodi semi-formali.

Ad esempio, per astrarre leggermente la condizione esaminata, supponiamo di voler trovare il valore intero più grande xper quale alcune condizioni poss(x) è vero. Anche questa chiarezza nella definizione del problema è più di quanto molti programmatori inizino. (Per esempio, poss(x) può essere a[x] ≤ v per un certo valore v; questo è per scoprire quanti elementi nella matrice ordinata a sono più grati di v, per esempio.) Quindi, un modo per scrivere la ricerca binaria è:

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);

È possibile aggiungere ulteriori dichiarazioni di asserzione e altri assegni, ma l'idea di base è che, poiché si aggiorna lo a mid  solo quando lo sai poss(mid) è vero, si mantiene invariato quello poss(lo) è sempre vero Allo stesso modo, hai impostato hi a mid solo quando poss(mid) è falso, quindi si mantiene invariato poss(hi) è sempre falso Pensa alla condizione di terminazione separatamente. (Si noti che quando hi-lo è 1, mid equivale a lo. Quindi non scrivere il ciclo come while(hi>lo), o avrai un ciclo infinito.) Alla fine del ciclo, sei garantito hi-lo è al massimo 1, e perché hai sempre mantenuto invariato (poss(lo) è vero e poss(hi) è falso), non può essere 0. Inoltre, ancora a causa della tua invariante, lo sai lo è il valore da restituire / stampare / utilizzare. Ci sono altri modi per scrivere la ricerca binaria, naturalmente, ma mantenere un invariante è un trucco / disciplina che aiuta sempre.


52
2018-06-18 01:49



Leggi questo. L'implementazione della ricerca binaria di Java ha nascosto un bug per quasi un decennio prima che qualcuno lo trovasse.

Il bug è un overflow intero. Non ha causato problemi alle persone perché quasi nessuno stava cercando strutture di dati abbastanza grandi.


13
2018-02-02 18:41



Se hai programmato le Perle nelle vicinanze, consulta il capitolo 4.

edit2: Come indicato nei commenti, è possibile scaricare il capitolo della bozza che ho citato sul sito dell'autore: http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html


7
2018-02-02 18:38



Un motivo fondamentale per cui le persone non possono implementare correttamente la ricerca binaria è che noi non caratterizzare bene la ricerca binaria, si tratta di un problema ben definito ma solitamente non lo si definisce bene.

Una regola universale è imparare dal fallimento. Qui, pensare a casi "non validi" aiuta a chiarire il problema. Cosa succede se l'input è vuoto? cosa succede se l'input contiene duplicati? dovrei implementarlo con un test condizionale o due test (più un test extra per la terminazione anticipata) per iterazione? e altri problemi tecnici come overflow / underflow numerico negli indici di calcolo e altri trucchi.

Errori che potrebbero essere evitati caratterizzando bene il problema sono gli errori Off-by-one e la gestione di elementi duplicati, come sottolineato da @Zach Scrivena.

Molte persone vedono la ricerca binaria come trovare un valore obiettivo dato un array ordinato. Ecco come viene usato il binario, non la ricerca binaria di per sé.

Cercherò di dare una definizione / formulazione rigorosa relativa della ricerca binaria e mostrerò un modo per scovare l'errore "fuori dalla porta" e duplicare i problemi, conformandosi a un approccio specifico, che, naturalmente, non è nuovo.

# (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

questa definizione risolve naturalmente il problema duplicato.

Ci sono comunemente due modi per indicare gli array, [] e [), io preferisco il secondo, un approccio di equivalenza di [) usa invece la coppia (start, count).

# 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

Quindi, se fai il tuo "se True, Recede (end)" e "se False, Avanti (inizio)" parte destra, hai quasi finito. Lo chiamo la "regola FFTR" della ricerca binaria. Se stai andando a trovare il primo oggetto, come nella definizione di cui sopra, a sinistra verrà avviato, tuttavia, a destra verrà avviato se si sta andando a trovare l'ultimo elemento. Io ti adeguo alla moda, quindi un possibile attrezzo è

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

lo convalida ulteriormente, prima mostra la convergenza e poi mostra la correttezza.

convergenza:

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.

correttezza:

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.

versione equivalente (inizio, conteggio),

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

riassumere, se conforme alla [) convenzione,

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

Per quanto riguarda la terminazione anticipata con un test extra, non penso valga la pena pagare, ma puoi provare.


2
2018-04-23 06:14



Non riuscendo a considerare che quando si calcola il punto medio tra due indici sommando i valori alto e basso si può verificare un overflow intero.

Riferimento


1
2018-02-02 18:41



L'architettura di pipeline dei processori moderni è molto più adatta per effettuare ricerche lineari rispetto alle ricerche binarie che hanno un sacco di decisioni e rami.

Quindi un comune bug di prestazioni e a ottimizzazione prematura (sai, queste sono la radice di tutti i mali) utilizza la ricerca binaria quando una semplice ricerca lineare sarebbe più veloce e, naturalmente, più semplice.

A seconda del numero di letture, persino l'ordinamento dei dati può rallentare le cose. Un punto di pareggio tra lineare e binario può facilmente essere a 1000 elementi per chiavi semplici (ad esempio numeri interi a 32 bit).


-1
2018-02-24 19:18