1. 首頁
  2. 問答
  3. 低+（高 - 低）/ 2便宜比（低+高）/ 2

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

2016-07-15 54 views
-1

我正在寫一個二進制搜索算法，我需要計算中間元素。有兩種方法二送中間元素如：低+（高 - 低）/ 2便宜比（低+高）/ 2

low+(high-low)/2

和

(low+high)/2

看來，低+（高 - 低）/ 2比（低+高）/ 2更有效，爲什麼？

來源

2016-07-15 Ryan

+2

請告訴我們它是如何更有效率？ – SomeDude

+0

@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

+0

這應該被標記爲重複。 –

相關問題

 相關問題