Verständnis binäre Suche Bug

Question

Ich versuche zu verstehen binäre Suche Bug mit byte Array, ich verstand das Konzept des Überlaufs, die bei der Berechnung der mid Index auftritt.

public byte binarySearch(byte[] arr, byte low, byte high, byte value){ 

     if(low>high){ 
      return -1; 
     } 

     /* Line 1 */ byte overflow_mid = (byte) (((byte) (low + high))/2); // This line giving overflow behaviour 

     /* Line 2 */ byte mid = (byte) ((low + high)/2);  // however this line doesn't, which is not what i expected 

     if(arr[mid]== value){ 
      return mid; 
     } 

     if(arr[mid]>value){ 
      return binarySearch(arr, low, (byte) (mid-1), value); 
     } 
     return binarySearch(arr, mid, high, value); 
    } 

Meine Intuition: Aber wenn ich das gleiche Verhalten mit byte Array simulieren wie folgt

Da niedrige und hohe Variablen vom Typ byte sind, glaube ich es nicht eine explizite Umwandlung zu byte müssen wieder während der Berechnung des Index Mitte in Zeile 2.

Dank

Answer 1

Sagen wir, dass byte low = 50, high = 100.

Der Ausdruck low + high wird zuerst beide zu int fördern, dann fügen Sie sie hinzu, resultierend in Wert 150 (int).

In Version 1 wird dann 150 (int) an byte übergeben. Dies ist der Wert -106 (byte). Überlauf. Wie für + wird der Operator / beide Seiten zu int fördern, so wird es -106 (int), das -53 (int) ist, wenn es durch 2 dividiert wird. Schließlich wirst du erneut in byte umgewandelt und landest mit -53 (byte).

In der Version 2, teilen Sie 150 (int) von 2, und da beide Seiten bereits sind int Werte, keine Förderung erfolgt, mit 75 (int) enden. Casting das zu byte gibt Ihnen 75 (byte). Kein Überlauf.

Answer 2

Du Gießen zwei sehr unterschiedliche Werte.

In deiner ersten Zeile machst du zwei Umwandlungen. Der erste überläuft. Sie übertragen das Ergebnis von low + high an Byte, was in Ihrem Fall überläuft.

jedoch in der zweiten Zeile sind Sie (low + high)/2 zu byte Gießen, und unter der Annahme sowohl low und high positiv sind, dass das Ergebnis bedeutet rlow < r < high sein und da sowohl low und high kann durch eine byte Variable dargestellt werden, deshalb So kann das Ergebnis r und es gibt keinen Überlauf.