为什么一个＆QUOT;懒惰的二进制搜索＆QUOT;？ [英] Why do a "Lazy Binary Search"?

问题描述

有人问起懒二进制今天搜索。不知道那是什么东西，我看着它，发现这个帖子：什么是懒惰的二进制搜索？ 从本质上讲，一个懒惰的二进制搜索是一个二进制搜索，您的不平等现象比较第一次，也是唯一比较平等一次 - 在结束

Someone asked about Lazy Binary Searches today. Not knowing what that was, I looked for it, and found this post: What is Lazy Binary Search? Essentially, a Lazy Binary Search is a Binary Search where you compare for inequalities first, and only compare for equality once - at the end.

有什么意义？在什么情况下检查是否 A＆LT; b 容易做到，但检查是否 A = B 是这么辛苦，你要为了避免它，如果可能吗？

What's the point? Under what circumstances is checking if A<B easy to do, but checking if A=B is so hard you want to avoid it if possible?

推荐答案

这是每次迭代少了一个比较。

It's one less comparison per iteration.

当然，这是在一个糟糕的平均运行时间为代价的（你没有得到的机会，提前返还）。 ¹ 但有时你在乎的是最坏情况下的运行时间（考虑硬 - 实时的应用程序，或者一个流水线硬件实现）。

Of course, that's at the expense of a worse average runtime (you don't get the opportunity to return early).¹ But sometimes all you care about is worst-case runtime (consider hard-real-time applications, or a pipelined hardware implementation).

<子> 1。虽然渐进的复杂性并没有改变。

这篇关于为什么一个＆QUOT;懒惰的二进制搜索＆QUOT;？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！