在二進制搜索中計算中點索引

因此，在二進制搜索中計算mid的正確方法是mid = low + ((high - low)/2)以便處理溢出錯誤。在二進制搜索中計算中點索引

我的實現使用無符號的64位變量，我從來沒有看到我的數組變得如此之大以致導致溢出的情況。我是否還需要使用上述實施方案或可以使用mid = (low + high)/2

這裏最好的做法是什麼？

2014-01-13 user1033777

@EdHeal我認爲這些工作了與 – templatetypedef

因素@EdHeal我道歉，如果我想的東西倒圓是相同的代數，甚至，但不要。在這兩種情況下出現相同的情況？ – templatetypedef

'低+（高 - 低）/ 2'也不保證是安全的。我研究支持負指數的代碼。積極的「高」和消極的「低」可能溢出「高 - 低」。 –

如果沒有溢出的可能性，計算中點的溢出安全方式在技術上是不必要的：如果您願意，可以使用不安全的公式。但是，無論如何，如果您的程序在某天被修改以打破您的假設，那麼保留它可能是一個好主意。我認爲添加一條CPU指令可以讓代碼具有面向未來的優勢，這對於代碼的可維護性來說是一項巨大的投資。

來源

2014-01-13 20:55:29 dasblinkenlight

另外：你永遠不知道什麼時候有人會剪切和粘貼你的代碼，並在別處使用它，你的假設不會飛。也許他們會在32位機器上運行它，並使用巨大的數組 - 或者其他東西。如果你知道* always *的編程習慣用法，那麼除非有充分的理由，否則不要用偶爾工作的編程習慣來替換它。（比在循環中保存幾個按鍵或2條機器指令更好）只需要$ 0。02 – JVMATL

檢查本文Nearly All Binary Searches and Mergesorts are Broken

更好的做法（今天）

可能更快，可以說是爲明確的是： 6：INT中旬=（低+高）>>> 1;

，之後：

在C和C++（您沒有>>>運營商），則可以做到這一點： 6：中期=（（無符號整型）低+（unsigned int）高））>> 1;

，並在結尾：

更新2008年2月17日：由於安東尼TRUX，諾基亞研究中心芬蘭的工程技術人員的主要成員爲指出，原來提出的修爲C和C++（第6行）不能保證按照相關的C99標準（國際標準--ISO/IEC - 9899 - 第二版 - 1999-12-01，3.4.3.3）工作，該標準說如果添加兩個有符號數量並獲得一個溢出，結果是未定義的。在這方面，較早的C標準，C89/90和C++標準都與C99相同。現在，我們已經取得了這種變化，我們知道程序是正確的;）

底線，時時會出現的時候，它不會工作

來源

2014-01-13 21:05:17 Dabo

鏈接文章中的Cherry採摘片段給出了錯誤的見解。那篇文章展示了微妙的錯誤在最糟糕的時間背後醜陋的頭，特別是在編程語言具有固定寬度整數的意想不到的規模。你的回答暗示代碼虛無主義（現在選擇任何作品，因爲它已經被打破了）而不是正確的外賣，避免這樣的錯誤是至關重要的。要麼使用無限精度的語言[Python]，要麼花時間理解低級語言的保證和未定義行爲，同時用斷言記錄程序限制。 – user13972

唐Knuth的方法，完美的作品通過的情況下，沒有溢出的可能性的位掩碼：

return (low & high) + ((low^high) >> 1)

來源

2018-01-20 04:39:01 coder

在二進制搜索中計算中點索引

回答

相關問題