1. Home
  2. 编程
  3. C++，二分查找法与斐波那切查找法效率对比

C++，二分查找法与斐波那切查找法效率对比

  • Bruce
    ACG

    总有人说斐波那切查找法在极大数据量情况下比二分查找法快，因为斐波那切查找法只有加减法，没有除法，然而二分查找法取中值完全可以右移1位center = (lo + hi)>>1来实现，位移操作是比加减法还要快的操作，因此我决定实践出真实

    PS：有个老哥已经做过实验了，在极大数据量情况下斐波那切查找法确实快一点，但是他的二分查找法是用除法实现的
    原贴：https://blog.csdn.net/fovwin/article/details/9077017
    本贴基于原贴代码，将除法改为位移，将C的callac操作改为C++的new，重新试验

    测试环境：

    CPU: R7 1700 @3.80GHz
    RAM: 32G
    OS: Windows Pro for Workstation 1909
    Compiler: MSVC 2019
    C++ standard: ISO C++17

    输入数据：长度为400,000,000的有序数组，array[i]=i
    对比方式：生成release版程序，从array中寻找数据4613841，用VS自带的性能探测器统计所需时间

    image.png
    二分查找法用时：521ms
    image.png
    534ms

    二分查找法险胜，二者差距几乎可以忽略不计，而数据输入的长度已经远超原贴实验中的长度了，且继续增加长度会引起数组上溢

    结论：两种算法在海量数据查找中性能差距可以忽略不计

    0
Log in to reply