Correzione del bug di ricerca binaria dal libro di Bentley (programmazione di perle: scrittura di programmi corretti)

Question

La ricerca binaria può essere implementata in molti modi: ricorsiva, iterativa, condizionale, ecc. Ho preso questo dal libro di Bentley "Perle di programmazione: scrittura di programmi corretti "che è un'implementazione iterativa e che include un bug.

public class BinSearch 
    { 
     static int search(int [] A, int K) { 
      int l = 0; 
      int u = A. length -1; 
      int m; 
      while (l <= u) { 
       m = (l+u) /2; 
       if (A[m] < K){ 
       l = m + 1; 
       } else if (A[m] == K){ 
        return m; 
       } else { 
        u = m-1; 
       } 
     } 
    return -1; 
    } 
} 

Ho trovato un errore nella riga m = (l + u)/2; può portare a overflow. Come possiamo evitare questo overflow in questa ricerca binaria?

Answer 1

provare quanto segue:

cambiamento

m = (l+u) /2

a

m = (u-l)/2 + l

Il motivo per cui la (l+u)/2 può traboccare diventa evidente se si considera una grande varietà di 2^31 - 1 elementi (valore massimo che può contenere un intero con segno a 32 bit). In questo caso la prima iterazione va bene perché 2^31 - 1 + 0 non è un grosso problema, ma si consideri il caso di l = m + 1 qui. Nella seconda iterazione è ancora lo stesso e l è 2^31/2 quindi l + u porterà a un overflow.

In questo modo si evita l'aggiunta di u + l determinando innanzitutto il centro relativo tra la e (u - l)/2 e quindi aggiungendo il numero inferiore l ad esso in modo che diventi assoluto. Quindi durante l'operazione m = (u-l)/2 + l; non superiamo mai il valore di u.

per riassumere il codice completo:

public class BinSearch 
{ 
    static int search(int [] A, int K) 
    { 
     int l = 0; 
     int u = A. length -1; 
     int m; 

     while (l <= u) 
     { 
      m = (u-l)/2 + l; 

      if (A[m] < K) 
       l = m + 1; 
      else if (A[m] == K) 
       return m; 
      else 
       u = m - 1; 
     } 
     return -1; 
    } 
} 

Answer 2

Penso che si dovrebbe cambiare u = m-l; a u = m -1.

è 1 non l. --------- addtion ------ causa (l + u) può essere maggiore di 2^31-1 (se int è 32 bit), quindi potrebbe traboccare. quindi dovresti cambiare (l + u)/2 a l + ((u-l) >> 1), e u-l non può essere maggiore di 2^31-1.

Answer 3

Prova cambiando

m = (l+u)/2 

a

m = l + (u - l)/2 

È banale vedere che entrambi è uguale e anche la seconda istruzione impedisce l'overflow.

Answer 4

Supponiamo che l e tu siano entrambi in [0, 2^31-1]. Se l, u> = 2^30, allora (l + u)> = 2^31 è overflow. Per evitare ciò, utilizzare

m = l + (u-l)/2; 

. Per di più, può essere più ragionevole di scrivere ricerca binaria in questo modo:

public class BinSearch 
    { 
     static int search(int [] A, int K) { 
      int l = -1;    // index lower bound shift left by 1 
      int u = A.length;  // index upper bound shift right by 1 
      int m; 
      while (l + 1 < u) { 
       m = l + (u-l)/2; // avoid overflow 
       if (A[m] < K){ 
        l = m;   // keep A[l] < K 
       } else { 
        u = m;   // keep A[u] >= K 
       } 
      } 
      if ((u == A.length) || (A[u] != K)) return -1; 
      return u; 
     } 
    } 

Answer 5

Come molti altri hanno detto, la soluzione è semplice, certamente la più semplice che ho visto per un 100-punto di taglie!Ecco un altro, che ha una bella simmetria, anche se ci vuole un paio di cicli di clock:

m = (l >> 1) + (u >> 1) + (l & u & 1); 

Si consiglia di non maligne Bentley per "un errore" fino ad avere una migliore informazione. Quando scrisse quell'articolo per l'ACM (un po 'di tempo negli anni '80 credo), era pseudocodice e scriveva in C a 32 bit; non esistevano macchine con gigabyte di RAM. Anche se avessero, con 4 byte int, una macchina a 32 bit non può avere una matrice con più di 2^28 pollici. Pertanto l'indice più alto possibile è 2^28-1. Il raddoppio di questo valore non è non causa di overflow in int.

Ovviamente, è esattamente lo stesso con Java a 32 bit. È necessario il kludge spezzato di Java a 64 bit, un linguaggio che consente agli oggetti di dimensioni che si avvicinano a 2^64 ma limita gli indici a 2^32-1 al fine di far apparire questo "bug".

Quello che chiami bug è un cambiamento delle ipotesi operative. Ogni programma nell'universo manifesterà qualche tipo di difetto se l'ambiente cambia nel modo giusto.

Answer 6

L'esecuzione iterativa della ricerca binaria ha effettivamente un bug. cambiare m = (l+u)/2. Come altri hanno già detto, può comportare un overflow dei numeri interi. Sostituirlo con m = l + (u-l)/2.

Per esperienza, ho visto più volte l'implementazione buggy della ricerca binaria. Ricerca binaria anche se un semplice concetto di divisione e conquista può essere difficile da ottenere. È facile modificare il precedente incarico m. Spero che questo aiuti ...

Answer 7

Anche se Machtl e altri hanno già scritto il modo per superare il bug di overflow ma aggiungendo solo per ragioni di completezza

1. Usa int mid = (basso + alto) >> > 1; più veloce modo
2. E in C e C++ (dove non abbiamo la >>> operatore) mid = ((unsigned int) basso + (unsigned int) alto)) >> 1;