了解二进制搜索错误

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

我的直觉：

由于 low 和 high 变量的类型为 byte，我相信在计算 mid 索引时不需要再次显式转换为 byte 在第 2 行。

谢谢

Answer 1

您正在投射两个截然不同的值。

在你的第一行中，你进行了两次转换。第一个溢出。您正在将 low + high 的结果转换为字节，这在您的情况下会溢出。

但是，在第二行中，您将 (low + high) / 2 转换为 byte，并假设 low 和 high 均为正数，这意味着结果 r 必须是 low < r < high 并且由于 low 和 high 都可以用 byte 变量表示，因此结果 r 也可以并且没有溢出.

Answer 2

假设 byte low = 50, high = 100.

表达式 low + high 将首先将两者提升为 int，然后将它们相加，得到值 150 (int)。

在版本 1 中，您随后将 150 (int) 转换为 byte，即值 -106 (byte)。溢出。和+一样，/运算符会将两边提升为int，所以变成-106 (int)，除以[=22=就是-53 (int) ].最后你再次转换为 byte，以 -53 (byte).

结束

在版本 2 中，您将 150 (int) 除以 2，由于双方都已经是 int 值，因此不进行任何提升，最终得到 75 (int)。将其转换为 byte 会得到 75 (byte)。 没有溢出.

了解二进制搜索错误

Understanding Binary Search bug

java

algorithm

debugging

byte

binary-search-tree