问什么是懒惰的二进制搜索？

EN

据我所知，“懒惰二分搜索”只是"Binary search“的另一个名字。

贾斯汀错了。如果需要，通用binarySearch算法首先检查目标是否等于当前中间条目，然后再进行到左半部分或右半部分。延迟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，应该向左。左索引保持不变，右索引变为中索引-1，右=3-1= 2。完成此步骤。

第二个while循环：

left <= right，0 <= 2，我们进入第二个while循环。mid索引被重新计算：(0+2)/2=1，Mid = 1. At once我们做相等检查，目标11与索引1条目相同，11 == 11。我们找到了这个条目，留下了所有左右的中间索引(不要紧)，并中断了while循环，返回索引1。

现在我们使用惰性binazySearch算法跟踪这个搜索，初始数组的左/右索引设置与以前相同。

第一个while循环：

left < right，我们进入第一个while循环。Mid索引的计算方式与上面相同= 3。这次我们不在普通的binarySearch中进行相等性检查，而是与mid索引条目进行比较。比较只检查我们的目标11是否大于中间索引条目，让它们是否等于while循环之外的最末端。，所以我们发现11 < 21，右索引被重置为中间索引，right = 3。完成这一步。

第二个while循环：

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

第三个while循环：

left < right，0< 1，这一次我们必须再次进入while循环，因为它仍然满足while条件。Mid索引变为(0+1)/2=0，mid = 0。在比较目标11和中间索引条目2之后，我们发现它大于它(11 > 2)，左侧索引被重置为mid + 1，左侧=0+ 1 =1。完成这一步。

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

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

然而，在其他一些情况下，懒惰的binarySearch更可取，但它不在本例的上下文中。

(算法的推理部分是由我完成的，任何人想要复制请功劳)

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