原 "二分查找(Binary Search

首先,我们来看一个笔者的拙作,一段二分查找代码

//返回值是key的下标,如果A中不存在key则返回-1
template <class T>
int BinSearch(T* A, const T &key, int lo, int hi)
{
    int mid;

    while(lo<hi)
    {
        mid = lo + (hi-lo)/2;

        if(key < A[mid])
            hi = mid-1;
        else if(key > A[mid])
            lo = mid+1;
        else
            return mid;

        if(lo==hi && A[lo]==key)
            return lo;
    }
    return -1;
}

    可以证明,算法的时间复杂度为O(nlogn),考虑前面的系数的话,大致是O(1.5nlogn)。

    但是,这一实现仍有改进的余地。注意到循环只需要1次判断来决定是否转进到左侧,但需要2次判断来决定是否转进到右侧。也就是进入左、右分支前的关键码比较次数不等。

    而斐波那契查找正是优化了这点。利用斐波那契数来对传入的数组进行黄金分割,这样前半部分较多而后半部分较少。另外,进入前半部分继续搜索所需的判断只有一次,而进入后半部分继续搜索所需的判断却有两次。如此而来,我们人为造成的这种不平衡,反倒是助长了搜索成本的平衡。

template <class T>
int FibSearch(T* A, const T &key, int lo, int hi)
{
    int mid;
    Fib fib(hi-lo);     //构造一个斐波那契数的类
    while(lo<hi)
    {
        int len = hi-lo;

        while(fib.get()>len)
            fib.prev();     //如果当前的fib.get()返回值大于len,则取前一个斐波那契数
        mid = lo + fib.get() - 1;  //分割节点的下标

        if(key < A[mid])
            hi = mid-1;
        else if(key > A[mid])
            lo = mid+1;
        else
            return mid;

        if(lo==hi && A[lo]==key)
            return lo;
    }
    return -1;
}

    这里我们需要构造一个斐波那契数的类。要写好这个类,其实只需要一个数组,用动态规划的算法很好写,这里不再赘述。

    既然算法实现好了,我们就对这两种算法的正确性做个小测试吧:

int main()
{
    a=0,b=0;
    for(int i=0; i<=NUM; ++i)
    {
        A[i] = i;
    }

    for(int i=0; i<=NUM; ++i)   //正确性验证
    {
        if( BinSearch(A,i,0,NUM) != FibSearch(A,i,0,NUM) )
        {
            cout<<"What a fucking day !" <<i<<endl;
        }
    }
    return 0;
}

    算法性能对比(by fovwin):

参考资料:1.清华大学MOOC 《数据结构与算法》 by 邓俊辉,第二章

                 2.Wikipedia - Fibonacci Search Technique (https://en.wikipedia.org/wiki/Fibonacci_search_technique)

                 3.《"斐波那契查找"真的比二分查找快么?》 by forwin (强烈推荐,C语言实现,代码注释非常清晰 - http://blog.csdn.net/fovwin/article/details/9077017)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.5算法的分析之图灵机

No.5期 算法的分析之图灵机 小可:那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢? Mr. 王:有的,这里既然提到了多项式算法和易解难解问题,...

3808
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程1

前言 这里是一篇新手教程,环境是Xcode7+OpenGL ES 2.0,目标写一个OpenGL ES的hello world。 OpenGL ES系列教程在...

3379
来自专栏数据结构与算法

1570. [POJ3461]乌力波

★☆   输入文件:oulipo.in   输出文件:oulipo.out 简单对比 时间限制:1 s   内存限制:256 MB 【题目描述】 法国作家乔治·...

3107
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

2141
来自专栏码匠的流水账

聊聊leaky bucket算法的实现

1401
来自专栏用户2442861的专栏

阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

1462
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

1062
来自专栏人工智能LeadAI

TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

1764
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之训练模型

经过之前的训练数据的构建可以得到所有特征值为1的模型文件,本文将继续构建训练数据特征并构建模型。

1851
来自专栏ml

HDUOJ-------- Fibonacci again and again

   Fibonacci again and again Time Limit : 1000/1000ms (Java/Other)   Memory Limi...

35611

扫码关注云+社区

领取腾讯云代金券