在二分查找中mid =（beg + end）/ 2和mid = beg +（end-beg）/ 2之間有什麼區別？

從C++入門第五版問題3.26中是個問題，我不知道它們之間的區別嗎？可能是第二個可以避免溢出。在二分查找中mid =（beg + end）/ 2和mid = beg +（end-beg）/ 2之間有什麼區別？

2014-01-08 Pegasus

它甚至發生最好：Jon Bentley在Programming Pearls中的二進制搜索包含了這個溢出漏洞。 – TemplateRex

在計算數組中間時爲什麼選擇start +（end-start）/ 2 over（start + end）/ 2？ http://stackoverflow.com/questions/38688028/why-prefer-start-end-start-2-over-start-end-2-when-calculating-the） –

可能是第二個可以避免溢出。

沒錯。不能保證beg+end是可代表的;但在第二種情況下，中間值以及預期結果不大於end，因此不存在溢出的危險。

第二種形式也可以用於仿射類型，如指針和其他隨機訪問迭代器，它們可以被減去以給出距離，但不會被加在一起。

來源

2014-01-08 14:58:45

有趣的是，指針的空間（和隨機訪問iterat ors）到一個範圍是一個仿射空間：所以隨機訪問迭代器的仿射組合（就像取平均值）是一個邏輯上有效的事情。我們在C++中只缺少仿射組合原語。 – Yakk

@Yakk：謝謝，我正在絞盡腦汁想起單詞「affine」。自從我研究純粹的數學已經太久了。 –

這是一件很好的事情要記住。 – Yakk

一般情況下，這兩個表達式都是無效的。例如，第一個表達式是無效的，因爲對於指針或迭代器，不存在+這樣的操作。如果使用非隨機訪問迭代器，則第二個表達式無效。例如，當使用雙向迭代器時。

所以在C++正確的建設將看看下面的方式

mid = std::next(beg, std::distance(beg, end)/2);

來源

2014-01-08 15:05:16

你想在非隨機訪問迭代器上運行二進制搜索？ –

這不僅是我。但是C++標準聲明std :: binary_search與轉發迭代器 template bool binary_search（ForwardIterator first，ForwardIterator last， const T＆value）; –

我想如果比較函數非常昂貴，這是有意義的。通常它是沒有意義的，因爲你失去了運行時間的O（log n）界限。 –

如果我們考慮在一個比較通用的設置兩條線，不相關的二進制搜索，以下意見可以提出：

第二種形式試圖避免的問題是溢出，試圖表示一個大於最大可表示數字的數字，這是正確的。

對於單個數字的大小和結尾數量沒有限制，因此它們可能都大於最大可表示數字的一半。添加它們意味着中間結果（beg + end）可能溢出。

第二個解決方案似乎消除溢出的風險，但引入了一個又一個。如果值是有符號值，它們的區別可以再次溢出（或下溢，這取決於他們的標誌）。無符號值沒有問題。

還有另一種解決方案，你沒有張貼：

mid = beg/2 + end/2

它解決了溢和下溢的每一個問題，但引入了精度損失的一個新問題。如果與整數值工作，通過2分割可以通過0.5得到的結果斷，將這些一起，意味着中間可由1處於關閉狀態：

mid = 3/2 + 5/2; // mid is 3, instead of the 4 expected

與浮點值工作具有其他精度問題。

再回到手頭的問題，二進制搜索，可以很容易地看到，乞討和終點是無符號的值，所以第二個解決方案將總是給出正確的結果。

來源

2014-01-08 17:09:29 Tibos

答案是在書：

「由於從迭代結束返回不表示元件，它可能不增加或取消引用。「

圖形是有意義作爲不對稱範圍， [開始，現成的，端）或半開區間。

從加速C++，28頁，科尼格。

來源

2017-06-25 23:12:18 Lee

在二分查找中mid =（beg + end）/ 2和mid = beg +（end-beg）/ 2之間有什麼區別？

回答

相關問題