Понимание двоичного поиска ошибка

Question

Я пытаюсь понять двоичный поиск ошибка с byte массив, я понял понятие переполнения, которое происходит при вычислении индекса mid. Однако, когда я моделировать такое же поведение с помощью byte массива следующим образом:

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

Интуиция:

Поскольку низкие и высокие переменные типа byte, я считаю, что не нужно явное приведение byte снова при расчете индекса в серединев строке 2.

Благодарности

Answer 1

Скажет, что byte low = 50, high = 100.

Выражение low + high будет сначала рекламировать как int, затем добавить их, в результате чего значение 150 (int).

В версии 1 вы затем набрасываете 150 (int) на byte, что является значением -106 (byte). Переполнение. То же, что и для +, оператор / будет продвигать обе стороны до int, поэтому он становится -106 (int), что равно -53 (int), если делиться на 2. Наконец, вы снова добавили byte, в итоге получилось -53 (byte).

В версии 2, вы разделите 150 (int) на 2, и поскольку обе стороны уже int ценности, не продвижение по службе не будет сделано, в конечном итоге с 75 (int). Кастинг, который до byte дает вам 75 (byte). Отсутствие переполнения.

Answer 2

Вы литье две очень разных значений.

В вашей первой строке вы делаете две броски. Первый переполняется. Вы делаете результат low + high байтом, который переполняется в вашем случае.

Однако в вашей второй линии вы литье (low + high)/2 к byte, и предполагая, как low и high положительны, что означает, что результат r должен быть low < r < high и так как low и high может быть представлена ​​byte переменным, поэтому так может получиться результат r, и переполнения нет.