binary-search - 什么是惰性二进制搜索？

Question

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

比方说，我们有这个数字数组:

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

如何使用 Lazy Binary Search 查找数字 11？

Answer 1

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

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 循环:

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

第二个 while 循环:

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

现在我们通过 lazy binazySearch 算法跟踪这个搜索，初始数组的左/右索引设置与之前相同。

第一个 while 循环:

左<右，我们进入第一个while循环。 Mid index 的计算方法与上面相同 = 3。并且比较只检查我们的目标 11 是否大于中间索引条目，将它们是否相等留在 while 循环的最后。 所以我们发现 11 < 21，右索引重置为mid index, right = 3. 完成这一步。

第二个 while 循环:

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

第三个 while 循环:

left < right, 0 < 1，这一次我们又要重新进入while循环，因为它仍然满足while条件。 mid index变为(0+1)/2=0，mid = 0。比较target 11和mid index entry 2后发现它大于它(11 > 2)，left index重置为mid + 1，left = 0 + 1 = 1。完成这一步。

left index = 1 right index = 1，left = right，while循环条件不再满足，无需重新进入。我们进入下面的 if 部分。目标 11 等于左索引条目 11，我们找到目标并返回左索引 1。

如您所见，lazy binarySearch 再执行一个 while 循环步骤，最终实现索引实际上是 1。这就是我在一开始提到的定义中“推迟相等性检查”一词的含义。显然，惰性 binarySearch 算法在到达程序终止之前比普通的 binarySearch 做了更多的事情。 而“惰性”一词体现在何时检查目标等于索引条目的中间值。

然而，lazy binarySearch 在某些其他情况下更可取，但不在这种情况下。

(算法推理部分由本人完成，如需转载请注明出处)

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