为什么做一个“懒惰的二进制搜索”？

今天有人询问了懒惰二进制搜索。不知道那是什么，我看着它，发现这个帖子：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

回答