为什么选择"懒惰二进制搜索"？

Question

今天有人问起Lazy Binary Searches.不知道那是什么,我找了它,发现这篇文章:什么是懒二进制搜索？从本质上讲,惰性二进制搜索是一种二元搜索,您首先比较不等式,并且只比较一次的相等性 - 最后.

重点是什么？在什么情况下检查是否A<B容易,但检查是否A=B如此困难,你想尽可能避免它？

Answer 1

每次迭代的比较少一个.

当然,这是以较差的平均运行时间为代价的(您没有机会提前返回).¹ 但有时您关心的是最坏情况的运行时(考虑硬实时应用程序或流水线硬件实现).

_{虽然渐近的复杂性没有改变.}