我试图理解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)
。 没有溢出。