该算法如何按预期工作?尽管溢出

How is this algorithm working as expected? Despite the overflow

提问人:userNotFound 提问时间:3/9/2019 最后编辑:Dillon DavisuserNotFound 更新时间:3/10/2019 访问量:55

问:

我正在尝试解决这个问题:

给定一个非空的二叉搜索树和一个目标值,找到 BST 中最接近目标的值。

注意:给定的目标值是一个浮点数。您保证 BST 中只有一个最接近目标的唯一值。

这是我在网上看到的一个解决方案:

public int closestValue(TreeNode root, double target) { 
        int ret = root.val;
        while(root!=null) {
            if(Math.abs(target - root.val)  > Integer.MAX_VALUE){
                System.out.println( " Underflow!");
            }
            if(Math.abs(target - root.val) < Math.abs(target -ret)){
                ret = root.val;
            }
            root = (target < root.val)? root.left : root.right;
        }
        return ret;

    }

我正在考虑测试用例:

[1500000000,1400000000] 
-1500000000.0

其中 是父节点,是左子节点,是目标节点。Id 期望代码在 Math.abs 子句中下溢(确实如此),因为它大于 Int.MIN_VALUE。但是我不明白算法怎么还能返回.下溢不应该导致比较失败吗?15000000001400000000-1500000000.0-1500000000 - 15000000001400000000

java 算法 不可知的 二进制搜索树

评论

1赞 Josh 3/9/2019
target是 ,因此任何涉及它和 an 的表达式都将导致 被提升为 .此表达式在循环的第一次迭代中不成立:doubleintintdoubleMath.abs(target - root.val) > Integer.MAX_VALUE
0赞 userNotFound 3/9/2019
@Aldert,添加了目标值。
0赞 Dillon Davis 3/10/2019
@Selindek用我从逐字复制帖子的第三方收集的信息更新了问题陈述的问题。

答: 暂无答案