什么是懒惰二进制搜索？

Question

我不知道术语"懒惰"二进制搜索是否有效,但我正在阅读一些旧资料,我只是想知道是否有人可以解释懒惰二进制搜索的算法并将其与非惰性二进制文件进行比较搜索.

比方说,我们有这一系列的数字:

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

如何11使用Lazy Binary Search查找号码？

Answer 1

贾斯汀错了.常见的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循环.我们通过整数除法计算中间指数(0 + 7)/2=3.5=3,中间= 3. 直接我们检查目标11是否等于中间索引条目,11!= 21,然后我们决定是否向左或向右,我们发现11 <21,应该向左走.左侧索引保持不变,右侧索引变为中间索引-1,右侧= 3 - 1 = 2.完成此步骤.

第二次循环:

左<=右,0 <= 2,我们进入seond while循环.中秋节指数recalcuated:(0 + 2)/ 2 = 1,中= 1.在一次我们做的平等检查,目标11是一样的指标1项,11 == 11.我们发现该条目,留下所有左右中间索引(不关心)并打破while循环,返回索引1.

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

第一次循环:

左<右,我们进入第一个while循环.中间索引的计算方法与上面相同= 3. 不要在常见的二进制搜索中进行相等性检查,而是这次与中间索引条目进行比较.并且比较仅检查我们的目标11是否大于中间索引条目,留下它们是否等于或不在while循环之外的最末端.因此我们发现11 <21,右侧索引重置为中间索引,右侧= 3.完成此步骤.

第二次循环:

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

第三个循环:

左<右,0 <1,这次我们必须再次重新进入while循环,因为它仍然满足while条件.中间索引变为(0 + 1)/ 2 = 0,中间= 0.在将目标11与中间索引条目2进行比较后,我们发现它大于它(11> 2),左侧索引重置为中间+ 1,左侧= 0 + 1 = 1.完成此步骤.

左索引= 1且右索引= 1,左=右,而循环条件不再满足,因此无需重新输入.我们属于下面的if部分.目标11等于左索引条目11,我们找到目标并返回左索引1.

正如你所看到的,懒惰的binarySearch再做一个while循环步骤,最终实现索引实际为1.这就是"推迟等式检查"这个词在我刚才提到的定义中的含义.很明显,懒惰的binarySearch算法在到达程序终止之前比常见的binarySearch做更多的事情.术语"懒惰"反映在何时检查目标等于中间索引条目的时间.

但是,懒惰的binarySearch更适合在其他情况下使用,但它不在本案例的上下文中.

(算法的推理部分由我完成,任何人都希望复制请做信用)

来源:Sesh Venugopal,Prentice Hall撰写的"Java之外的数据结构"