无分快速平均

int mid = (low + high) >>> 1;

建议使用“(低+高)/2”进行中点计算。 won't work correctly 当整数溢出成为问题时。

下面是一个不受溢出问题影响的平均值的黑客版本:

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}

您可以使用位移位,还可以克服可能出现的溢出问题:

low + ((high-low) >> 1)

不过,我必须承认,我希望现代的编译器和口译员将2除法(或2的任何其他常量除法)作为比特移位,所以不确定它是否真的有帮助-试试看。

进一步扩展nils的答案 理查德·施罗佩尔 发明了这个。

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

项目23(Schroeppel):

(a和b)+(a或b)=a+b=(a xor b)+2(a和b)。

(A + B)/2 = ((A XOR B) + 2(A AND B))/2
          =  (A XOR B)/2  + (A AND B)
          =  (A XOR B)>>1 + (A AND B)


avg(x,y){return((x^y)>>1)+(x&y);}

(A AND B) + (A OR B) = A + B 因为 A AND B 给出(A和B之间)两种权力的总和, A OR B 既给那些共享的,也给那些不共享的,因此:

(A AND B) + (A OR B) = 
   (sum of shared powers of two) + 
   ((sum of shared powers of two) + (sum of unshared powers of two)) = 
     (sum of shared powers of two) + 
     ((sum of shared powers of two) + (sum of powers of two of A only) + 
     (sum of powers of two of B only)) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B 给出了这些位在A和B之间的映射。因此,

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

因此:

2(A AND B) + (A XOR B) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.

如果我记得正确的话,在某些情况下,使用数组的确切中间位置实际上会变慢。解决方案是随机化对数组进行二等分的索引的选择。同样适用于确定数组中值的算法。

我记不起确切的细节,但我记得在 MIT algorithms series 在iTunes上。

尝试低+(高-低)/2)。这应该有效,因为你只取了两个数字的平均值。如果二进制搜索列表很大,这将减少算法所需的时间,因为高-低比高+低小得多。