文档章节

数据结构(六)查找---有序表查找(三种查找方式:折半,插值,斐波拉契查找)

o
 osc_3md1xrlp
发布于 2018/08/19 00:29
字数 1984
阅读 13
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

前提

有序表查找要求我们的数据是有序的,是排序好的,我们只需要进行查找即可

我们下面将介绍折半查找(二分查找),插值查找,斐波那契查找

一:折半查找

(一)定义

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

(二)查找过程

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

(三)代码实现

int Binary_Search(int *a, int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low<=high)
    {
        mid = (low + high) / 2;
        if (a[mid] < key)
            low = mid + 1;
        else if (a[mid]>key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

int main()
{
    int a[10] = { 1, 6, 12, 21, 30, 31, 32, 42, 49, 52 };
    int index;
    index=Binary_Search(a, 10, 49);
    if (index != -1)
        printf("find key in %d\n", index);
    else
        printf("not find key\n");
    system("pause");
    return 0;
}

(四)性能分析

其时间复杂度是O(logn),不过由于折半查找的前提是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,这样的算法是比较好的。但是对于需要频繁插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,不建议使用。

二:插值查找(按比例查找法)

(一)算法分析:

对于前面的折半查找,为啥一定要折一般,而不是1/4或者其他?
比如:我们查字典Apple,我们会先从中间查找,还是有一定目的的向前找。
或者在0
-1000个数之间有200个元素从小到大均匀分布排序,我们若是需要查找到15,我们会去中间查找500,还是直接去前面开始查找。 以上都说明我们上面的折半查找可以再进行改进

首先我们对折半公式进行改写:

 

折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的),其前面的查找系数(比例参数)始终是1/2

通过类比,我们可以将查找的点改进为如下:

也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。

(二)基本思想:

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,插值查找也属于有序查找。

(三)代码实现:

int Insert_Search(int *a, int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = low + (key - a[low]) / (a[high] - a[low])*(high - low);
        if (a[mid] < key)
            low = mid + 1;
        else if (a[mid]>key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}
实现方法和折半一样,只是修改了mid

(四)性能分析:

而插值查找则比较灵活,并不是简单的从中间进行的,它是根据我们需要查询的值的渐进进行搜索的.

插值查找的不同点在于每一次并不是从中间切分,而是根据离所求值的距离进行搜索的.
对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
时间复杂度:平均情况O(loglog(n)),最坏O(log(n))

三:斐波那契查找(仅使用加法减法实现二分查找)

除了插值查找之外,我们再介绍一种有序查找,可以对折半进行优化,那就是斐波那契查找,利用了黄金分割原理来实现的
斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,即n=F(k)-1;

(一)斐波那契数列

越向后,每两个数之间相除越接近黄金比例

(二)斐波拉契查找实现

1.首先我们要创建一个斐波拉契数列

2.获取我们的数组大小n(我们不考虑0下标,因为我们的斐波那契数列从0开始,无法构成黄金比例),在斐波拉契数列中的位置

例如上面的查找数组大小为n=10,F[6]<n<F[7],所以得出其位置为k=7

3.因为我们的k=7,F[7]=13,而a数组最大为10,我们需要对其按照F[7]=13补齐数组,使其长度为F[7]-1=12,将a[11]=a[10],a[12]=a[10]

4.开始正式查找,按照上图mid=low+F[k-1]-1;

 

(三)思考:n=F(k)-1, 表中记录的个数为某个斐波那契数小1。这是为什么呢?

 推文:斐波那契查找原理详解与实现

是为了格式上的统一,以方便递归或者循环程序的编写。
表中的数据是F(k)-1个,使用mid值进行分割又用掉一个,那么剩下F(k)-2个。
正好分给两个子序列,每个子序列的个数分别是F(k-1)-1与F(k-2)-1个,格式上与之前是统一的。
不然的话,每个子序列的元素个数有可能是F(k-1),F(k-1)-1,F(k-2),F(k-2)-1个,写程序会非常麻烦。

(四)算法实现

void Fibonacci(int **Fb, int n)
{
    int f1, f2,ft;
    int count=3;
    f1 = 1; f2 = 1;

    while (f2<n)
    {
        ft = f1 + f2;
        f1 = f2;
        f2 = ft;
        count++;
    }
    (*Fb) = (int *)malloc(count*sizeof(int));
    (*Fb)[0] = 0;
    (*Fb)[1] = 1;
    for (f1 = 2; f1 <= count - 1; f1++)
        (*Fb)[f1] = (*Fb)[f1 - 1] + (*Fb)[f1 - 2];
}
创建斐波那契数列
int Fibonacci_Search(int *a, int n, int key)
{
    int low, high, mid, i, j,k;
    int *Fb,*temp;
    //根据实际情况来初始化
    low = 1;
    high = n;

    Fibonacci(&Fb, n);
    k = 0;

    while (n > Fb[k])    //计算n位于斐波那契数列位置
        k++;

    temp = (int *)malloc((Fb[k] - 1 + 1)*sizeof(int));//后面加1是因为还有个下标0空间
    memcpy(temp, a, n*sizeof(n + 1));

    for (i = n + 1; i <= Fb[k] - 1; i++)    //我们要查找的是数组1到F[k]-1,而实际数组长要包括一个下标0空间
        temp[i] = a[n];

    while (low<=high)
    {
        mid = low + Fb[k - 1] - 1;
        if (key == temp[mid])
        {
            //分情况,是前半段,正常输出,后半段判断是不是在我们补充的数组里面,这时我们返回原数组最后一个下标
            if (mid <= n)
                return mid;
            else
                return n;
        }
        else if (key>temp[mid])
        {
            low = mid + 1;
            k = k - 2;
        }
        else
        {
            high = mid - 1;
            k = k - 1;
        }
    }
    return 0;    //0是未找到,0下标使无意义的
}
int main()
{
    int a[11] = { 0,1,16,24,35,47,59,62,73,88,99};
    int index;
    index = Fibonacci_Search(a, 10, 73);
    if (index != -1)
        printf("find key in %d\n", index);
    else
        printf("not find key\n");
    system("pause");
    return 0;
}

 (五)性能分析

其时间复杂度也是O(logn),就平均性能来说,斐波那契查找由于折半查找。但是若是最坏情况,比如key=1,始终处于左侧长半区查找,则效率低于折半查找。

四:总结

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
6.1K
18
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.7K
0
树莓派(Raspberry Pi):完美的家用服务器

自从树莓派发布后,所有在互联网上的网站为此激动人心的设备提供了很多有趣和具有挑战性的使用方法。虽然这些想法都很棒,但树莓派( RPi )最明显却又是最不吸引人的用处是:创建你的完美家用...

异次元
2013/11/09
7.4K
8
5分钟 maven3 快速入门指南

前提条件 你首先需要了解如何在电脑上安装软件。如果你不知道如何做到这一点,请询问你办公室,学校里的人,或花钱找人来解释这个给你。 不建议给Maven的服务邮箱来发邮件寻求支持。 安装Mav...

fanl1982
2014/01/23
1.2W
7
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2

没有更多内容

加载失败,请刷新页面

加载更多

创建具有列表理解的字典 - Create a dictionary with list comprehension

问题: I like the Python list comprehension syntax. 我喜欢Python列表理解语法。 Can it be used to create dictionaries too? 它也可以用来创建字典吗? For example, by iterating over......

技术盛宴
今天
15
0
从JS数组中删除重复的值[duplicate] - Remove duplicate values from JS array [duplicate]

问题: This question already has answers here : 这个问题已经在这里有了答案 : Get all unique values in a JavaScript array (remove duplicates) (79 answers) 获取JavaScript数组中的......

法国红酒甜
今天
11
0
如何使用AngularJS在浏览器的控制台中访问$ scope变量?

问题: I would like to access my $scope variable in Chrome's JavaScript console. 我想在Chrome的JavaScript控制台中访问$scope变量。 How do I do that? 我怎么做? I can neither see ......

fyin1314
今天
18
0
ImageMagick - 添加水印

背景 最近制作思维导图想添加自己的水印,网上很多例子都是使用ImageMagick来完成。但是不少代码在本地并不可行。经过一番试验,找到两个方法。 方法一 代码 stackoverflow方法改良: conver...

wffger
今天
11
0
OSChina 周四乱弹 —— 到底是怎样的饕餮盛宴在等待着我!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐 :《你 能 來 保 護 我 的 世 界 嘛》- 歪门 《你 能 來 保 護 我 的 世 界 嘛》- 歪门 手机党少年们想听歌,请使劲儿戳(这里)...

小小编辑
今天
77
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部