什么是惰性二分搜索？

发布于 2024-11-06 04:29:31 字数 196 浏览 4 评论 0原文

我不知道术语“惰性”二分搜索是否有效，但我正在浏览一些旧材料，我只是想知道是否有人可以解释惰性二分搜索的算法并将其与非惰性二分搜索进行比较搜索。

假设我们有这个数字数组：

2, 11, 13, 21, 44, 50, 69, 88

如何使用惰性二分搜索查找数字 11？

原文

I don't know whether the term "Lazy" Binary Search is valid, but I was going through some old materials and I just wanted to know if anyone can explain the algorithm of a Lazy Binary Search and compare it to a non-lazy Binary Search.

Let's say, we have this array of numbers:

2, 11, 13, 21, 44, 50, 69, 88

How to look for the number 11 using a Lazy Binary Search?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

鱼忆七猫命九 2024-11-13 04:29:31

贾斯汀错了。
常见的二分搜索算法首先检查目标是否等于当前的中间条目，然后根据需要继续进行左半部分或右半部分。惰性二元搜索算法将相等性检查推迟到最后。

algorithm lazyBinarySearch(array, n, target)
left<-0
right<-n-1
while (left<right) do
    mid<-(left+right)/2
    if(target>array[mid])then
        left<-mid+1
    else
        right<-mid
    endif
endwhile

if(target==array[left])then
    display "found at position", left
else
    display "not found"
endif

在你的例子中，在一个数组中，

2 11 13 21 44 50 69 88

你想要搜索 11

首先我们进行常见的二分搜索，

index 0     1  2  3   4  5  6  7
      2     11 13 21  44 50 69 88
      left        mid          right

第一个 while 循环：

左 <= 右，我们进入第一个 while 循环。我们通过整数除法通过 (0+7)/2=3.5=3 计算出中间索引，mid = 3。立即我们检查目标 11 是否等于中间索引条目，11 != 21，然后我们决定向左走还是向右走，我们发现11 < 21、应该向左走。左索引保持不变，右索引变为中索引-1，右= 3 - 1 = 2。完成此步骤。

第二个while循环：

left <= right，0 <= 2，我们进入第二个while循环。重新计算 Mid 索引：(0+2)/2=1，mid = 1。立即我们进行相等性检查，目标 11 与索引 1 条目相同，11 == 11。我们找到了这个条目，留下所有左右中间索引（不关心）并打破 while 循环，返回索引 1。

现在我们通过惰性 binazySearch 算法跟踪此搜索，具有左/右索引的初始数组设置了与以前的。

第一个 while 循环：

left <对了，我们进入第一个 while 循环。中间索引的计算方式与上面相同= 3。这次我们没有在常见的二进制搜索中进行相等性检查，而是与中间索引条目进行比较。并且比较仅检查我们的目标 11 是否大于中间索引条目，将它们是否等于留在 while 循环之外的最后。因此我们发现 11 < 21、右索引重置为中索引，右= 3。完成此步骤。

第二个 while 循环：

left <对，0 < 3、我们进入第二个while循环。 mid 索引通过整数除法重新计算为 mid = (0+3)/2 = 1。 我们再次与中间索引条目 11 进行比较，我们意识到它不大于中间索引条目。我们进入 while 循环的 else 部分，并将 right 索引重置为 mid 索引，right = 1。完成这一步。

第三个 while 循环：

left <对，0 < 1、这次我们还得重新进入while循环，因为它仍然满足while条件。 Mid 索引变为 (0+1)/2=0，mid = 0。将目标 11 与 mid 索引条目 2 进行比较后，发现它大于它（11 > 2），将 left 索引重置为 mid + 1，left = 0 + 1 = 1。完成这一步。

当左索引=1，右索引=1时，左=右，while循环条件不再满足，所以不需要重新进入。我们进入下面的 if 部分。目标 11 等于左索引条目 11，我们找到了目标并返回左索引 1。

正如你所看到的，惰性二元搜索又做了一个 while 循环步骤，最终意识到索引实际上是 1。这就是“推迟相等”一词的用法check”的意思是我一开始提到的定义。显然，惰性二元搜索算法在到达程序终止之前比普通二元搜索做了更多的事情。 术语“惰性”反映在检查目标是否等于中间索引条目的时间。然而，

惰性二进制搜索在某些其他情况下更适合使用，但它不是在以下情况下使用：这个案例。

（算法的推理部分是我完成的，任何想要复制的人请注明出处）

来源：“Data Structures Outside In With Java”作者：Sesh Venugopal，Prentice Hall

Justin was wrong.
The common binarySearch algorithm first checks whether the target is equal to current middle entry before proceeding to the left or right halves if required. Lazy binarySearch algorithm postpones the equality check until the very end.

algorithm lazyBinarySearch(array, n, target)
left<-0
right<-n-1
while (left<right) do
    mid<-(left+right)/2
    if(target>array[mid])then
        left<-mid+1
    else
        right<-mid
    endif
endwhile

if(target==array[left])then
    display "found at position", left
else
    display "not found"
endif

In your case, in an array,

2 11 13 21 44 50 69 88

and you want to search for 11

First we do a trace of common binary search,

index 0     1  2  3   4  5  6  7
      2     11 13 21  44 50 69 88
      left        mid          right

First while loop:

left <= right, we enter the first while loop. We calculated the mid index by (0+7)/2=3.5=3 by integer division, mid = 3. straight away we check if target 11 is equal to the mid index entry, 11 != 21, then we decide whether to go left or right, we finds out 11 < 21, should go left. left index remains unchanged, right index becomes mid index -1, right = 3 - 1 = 2. Done this step.

Second while loop:

left <= right, 0 <= 2, we enter the seond while loop. Mid index is recalcuated: (0+2)/2=1, mid = 1. At once we do the equality check, target 11 is the same as the index 1 entry, 11 == 11. We found this entry, leaving behind all the left right mid indexes (don't care) and breaks out the while loop, return index 1.

Now we trace this search by lazy binazySearch algorithm, initial array with left/right indexes set up the same as previous.

First while loop:

left < right, we enter the first while loop. Mid index is calculated as the same above = 3. Instead of doing an equality check in common binarySearch we do a comparison with the mid index entry this time. And the comparison only checks if our target 11 is greater than the mid index entry, leaving whether they equal or not to the very end outside the while loop. So we find out 11 < 21, right index is reset to the mid index, right = 3. Done this step.

Second while loop:

left < right, 0 < 3, we enter the second while loop. mid index is recalculated as mid = (0+3)/2 = 1 by integer division. Again we do a comparison with mid index entry 11, we realise it's not greater than mid index entry. We fall into the else part of the while loop and reset the right index to be mid index, right = 1. Done this step.

Third while loop:

left < right, 0 < 1, this time we have to re-enter the while loop again since it still satisfies the while condition. Mid index becomes (0+1)/2=0, mid = 0. After comparing target 11 with mid index entry 2 we found out it's greater than it (11 > 2), left index is reset to mid + 1, left = 0 + 1 = 1. Done this step.

With left index = 1 and right index = 1, left = right, while loop condition is no longer satisfied, so there's no need to re-enter. We fall into the if part down below. Target 11 equals left index entry 11, we found the target and returns left index 1.

As you can see, lazy binarySearch does one more while loop step to finally realise the index is actually 1. And this is how the word "postpones the equality check" means in the definition I mentioned in the very beginning. Clearly the lazy binarySearch algorithm does more things than common binarySearch before reaching the program termination. And the term "lazy" is reflected in the time of when to check the target equals the mid index entry.

However lazy binarySearch is more preferable to use under some other circumstances, but it's not in the context of this case.

(The reasoning part of the algorithm is done by me, anyone wishes to copy please do credit)

source: "Data Structures Outside In With Java" by Sesh Venugopal, Prentice Hall

回复收藏 0 原文