首页 文章

了解二进制搜索错误

提问于
浏览 次
3

我试图理解 binary search 错误与 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行的 mid index 时，它不需要再次显式转换为 byte .

谢谢

java algorithm debugging byte binary-search-tree

2 回答

  • 1

    让我们说 byte low = 50, high = 100 .

    表达式 low + high 将首先将两者都提升为 int ，然后添加它们，从而产生值 150 (int) .

    在版本1中，然后将 150 (int) 转换为 byte ，其值为 -106 (byte) . Overflow . 与 + 相同， / 运算符将双方都提升为 int ，因此它变为 -106 (int) ，除以 2 时为 -53 (int) . 最后你再次投射到 byte ，结尾是 -53 (byte) .

    在版本2中，您将 150 (int) 除以 2 ，并且由于双方都已经 int 值，因此不会进行任何提升，最终会以 75 (int) 结束 . 将其转换为 byte 会给你 75 (byte) . No overflow .

    回复于
  • 2

    你投了两个非常不同的值 .

    在第一行中，'re making two casts. The first one overflows. You'将 low + high 的结果重新转换为byte，在您的情况下溢出 .

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

    回复于

相关问题