低+（高 - 低）/ 2便宜比（低+高）/ 2

java

2016-07-15 55 views -1 likes

-1

我正在写一个二进制搜索算法，我需要计算中间元素。有两种方法二送中间元素如：低+（高 - 低）/ 2便宜比（低+高）/ 2

low+(high-low)/2

和

(low+high)/2

看来，低+（高 - 低）/ 2比（低+高）/ 2更有效，为什么？

来源

2016-07-15 Ryan

请告诉我们它是如何更有效率？ – SomeDude

@svasa https://leetcode.com/problems/guess-number-higher-or-lower/我为这个问题写了两个解决方案，一个通过测试，另一个超出时间限制。 – Ryan

回答

-1

我找到了答案here。

在高和低两个都是非负的假设下，我们肯定知道最高位（符号位）为零。

所以高和低都是31位整数。

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 
low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

当你将它们加在一起时，它们可能会“溢出”到最高位。

high + low =  1000 0000 0000 0000 0000 0000 0000 0000 
      = 2147483648 as unsigned 32-bit integer 
      = -2147483648 as signed 32-bit integer 

(high + low)/2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824 
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

来源

2016-07-15 11:56:38 Ryan

这应该被标记为重复。 –

低+（高 - 低）/ 2便宜比（低+高）/ 2

回答

相关问题