爲什麼做一個「懶惰的二進制搜索」？

今天有人詢問了懶惰二進制搜索。不知道那是什麼，我看着它，發現這個帖子：What is Lazy Binary Search?從本質上講，一個懶惰的二進制搜索是您比較的不平等首先，只有比較平等一次二進制搜索 - 在最後。爲什麼做一個「懶惰的二進制搜索」？

有什麼意義？在什麼情況下檢查A<B是否容易做，但是檢查A=B是否如此困難，如果可能你想避免它？

2012-03-03 zmbq

這是每次迭代少了一個比較。 – 2012-03-03 22:15:45

以更多迭代爲代價。 – zmbq 2012-03-03 22:24:03

確實。但有時您關心的只是最壞情況的性能（考慮硬實時應用程序或流水線硬件實現）。 – 2012-03-03 22:26:08

這是每次迭代少了一個比較。

當然，這是在一個糟糕的平均運行的費用（你沒有得到的機會，提前返回）。但是，有時您關心的只是最壞情況運行時（考慮硬實時應用程序或流水線硬件實現）。

_{1.雖然漸進的複雜性並沒有改變。}

2012-03-03 22:41:38

我仍然保持'懶'是一個壞名字。它應該被稱爲ConsistentBinarySearch什麼的。啊，至少現在是有道理的。謝謝。 – zmbq 2012-03-03 22:42:57

那麼，它只是在「偷懶」進行搜索，你跳過每次X元素比較中心的元素時檢查是否相等。只是在最後纔會檢查平等。我想你所做的一切是減少一個==條件的搜索。

2012-03-03 22:18:43 noMAD

但是你正在增加迭代次數。也許'懶惰'對它來說只是一個壞名字？ – zmbq 2012-03-03 22:24:32

我不明白。你爲什麼說迭代次數會增加？ – noMAD 2012-03-03 22:29:59

因爲您總是迭代到結束 - log2（系列的長度）次。在此之前，你永遠不會停止，即使你正在尋找的物品是在第一次迭代中找到的。 – zmbq 2012-03-03 22:33:19

懶惰搜索所做的一件事是找到第一個元素與序列中的元素等於目標（假設目標在序列中）。

如果有匹配的目標是幾個要素，一個非懶搜索會得到你的任何一個。

因此，C++庫的binary_search可以實現爲非懶惰（我想它通常是），而lower_bound不能。

2012-03-03 22:32:08

是的，這是一個很好的副作用，但它可能不是他們想到的，當他們將它命名爲「懶惰」而不是「LowestAnswerBinarySearch」時。 – zmbq 2012-03-03 22:36:08

嗯，問題是「爲什麼使用它」，而不是「爲什麼叫懶惰」。即便如此，這些東西並不總是以結果的屬性來命名，但有時候以它的工作方式來命名。「懶」更容易引導。 – 2012-03-03 22:56:30

此外，似乎「懶惰二進制搜索」不是一個非常廣泛使用的術語。根據不太全面的谷歌搜索，我看到它使用的唯一地方是詢問它是什麼（這裏是SO）以及羅格斯大學特定課程的講座和作業。 – 2012-03-03 23:08:00

回答