中点公式溢出错误 [英] Midpoint Formula Overflow Error

问题描述

我正在学习算法/大o，我对此很好奇。

I'm learning algorithms/big o and i was just curious about this.

使用

 mid = (low+high)/2;

以获取二进制搜索算法的中点，因为可能会发生溢出错误。

in order to get the midpoint for a binary search algorithm is generally discouraged because of the possibility of an overflow error. Why would this cause an overflow error to occur, and how does

 mid = low + (high-low)/2;

预防此错误？

谢谢。

推荐答案

在第一种情况下，您计算的值（低+高）可能太大而无法容纳为int值，如果低和高都足够大（例如，如果两者都等于2 ^ 30 + 1 /甚至更大/）。在第二种情况下，您无需进行计算（低+高），而是做一个小技巧，然后遍历表达式（高-低），该表达式相对于int溢出要安全得多。

In the first case you calculate the value (low+high) which might be too huge to fit into an int, if low and high are both huge enough (say if both are equal to 2^30+1 /or even greater/). In the second case, you don't calculate (low+high), you do a small trick and you go through the expression (high-low) and that expression is much safer with respect to int overflow.

不过，如果您没有大小大于2 ^ 30的数组（无论如何，这都是一个很大的数组），我不知道您如何即使使用第一个表达式，也可能会遇到int溢出。因此，在大多数情况下，我只会使用第一个而不用担心。

Still, if you don't have an array whose size is greater than 2^30 (which is quite a huge array anyway), I don't see how you can run into an int overflow even when using the first expression. So I would just use the first one in most cases and not worry.

这篇关于中点公式溢出错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！