斐波那契搜索速度比二分搜索快吗？

Question

我读了一些声称Fibonacci搜索平均比二分搜索快的材料,主要原因是"它只涉及加法和减法,而不是除以2".

我有一些问题:

1.斐波那契搜索比二进制搜索更快,而不考虑操作速度吗？因为二进制搜索的步骤较少.

2.除以2可以通过位移操作来完成,它是否真的慢于加法？

3.与二进制搜索相比,斐波那契搜索的优势是什么？

Answer 1

Fibonacci搜索速度比二进制搜索更快而不考虑操作速度吗？因为二元搜索的步骤更少.

它取决于列表的底层存储系统.例如 - 想想一个磁盘.在先前读取的一个圆柱体中查找位置要"更便宜" - 因为读取臂不必移动.因此,如果您的读取彼此更接近 - 您更可能需要更少地移动读取臂 - 因此每个磁盘搜索的预期时间更短.此外,将读取臂移动到较小的汽缸上同样比将其移动到更多汽缸上更快

在示例中:

将读取臂从(1)移动到(2)比从(1)到(3)移动要便宜得多.并且由于(2)是"更接近"(在地址方面)然后(3),更短的跳跃更可能属于这一类别.[从(1)到(2)读取臂根本不会移动,它只会让磁盘旋转直到它到达它]

除以2可以通过位移操作完成,它是否真的慢于加法？

这主要是硬件(和编译器优化)问题.我无法想象为什么制造商不会进行这种优化的任何原因,我所知道的大多数实现中的位移与添加一样快.

与二元搜索相比,斐波纳契搜索的优势是什么？

如(1)中所述 - 连续磁盘搜索之间的较短距离导致较短(预期)的寻道时间.