我试图理解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,我相信在计算第2行的中索引时,不需要再次显式转换为byte

谢谢

最佳答案

可以说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)没有溢出

07-24 09:51
查看更多