数据结构--有序表查找

一、查找表
1、定义
A.查找表(table):由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素间存在完全松散的关系,因此查找表是非常灵便的数据结构,他是在实际应用中被大量使用的数据结构。
B.关键字(key):元素中某个数据项的值,用于标识一个数据元素,若关键字可唯一的标识一个记录,则为“主关键字(primary key)”,若能标识若干记录,则为“次关键字(secondary key)”
C.查找:根据给定值,在查找表中确定一个其关键字 = 给定值的元素,如存在这一的记录,则查找是成功的

2、查找表的操作
A.静态查找表:查询某个“特定的”数据元素是否在查找表中,检索某个“特定的”数据元素的各种属性
B.动态查找表:在查找中同时插入查找表中不存在的元素,从查找表中删除一存在的元素

二、静态查找表
1、顺序表的查找
从表中第n个记录开始,逐个进行关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功。查找之前需要设置对r[0]的关键字赋值K,免去查找过程中每一步都要检测整个表是否查找完毕,起到了监视哨的作用,当然监视哨也可以设在高下标出。
顺序查找的缺点:平均查找长度较大,尤其当n特别大时,查找效率低。
顺序查找的优点:算法简单,适用面广,对表的结构物要求。

/* a为数组,n为要查找的数组长度,key为要查找的关键字 */
int Sequential_Search(int *a, int n, int key){
    for (int i = 0; i < n; i++){
        if (a[i] == key)
            return i;
    }
    return 0;
}
//顺序查找优化(有哨兵的顺序查找)
int Sequential_Search2(int *a, int n, int key){
    int i;
    /* 设置a[0]为关键字值,我们称之为“哨兵” */
    a[0] = key; 
    /* 循环从数组尾部开始 */
    i = n;     
    while (a[i] != key){
        i--;
    }
    /* 返回0则说明查找失败 */
    return i;   
}

有哨兵的顺序查找比普通查找少了一个比较(for循环中的i < n),因此在大量数据的情况下,有哨兵的顺序查找比普通顺序查找要快。
2、有序表的查找
A.折半查找:先确定待查记录所在范围(区间),然后逐步缩小范围,直到找到或找不到记录为止。
举例:05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92有序表中中查找21和85
设指针low,hig为待查元素所在范围的下界和上界,指针mid为指示区间的中间位置,即mid = [(low + hig) / 2],此处,low何hig的初值为1和11,即[1, 11]为待查范围。
先查找K=21:


image.png

首先r[mid].key与K比较,由于r[mid].key > K,说明若待查元素存在,必在区间[low, mid - 1]范围内,则指针hig指向第mid - 1个元素,重新求得mid = [(1 + 5) / 2] = 3


image.png

r[mid].key与K比较,由于r[mid].key < K,说明待查元素若存在,必在[mid + 1, hig]范围内,则这种low指向第mid + 1个元素,mid新值为4,比较r[mid].key与K,相等,查找成功
image.png

再看K = 85:
image.png

此时low > hig,说明没有关键字为K的元素,查找失败。
算法:
static int BinarySearch(int [] a, int n, int key) {
    int low, high, mid;
    low = 0;
    high = n;
    while(low <= high){
        mid = (low + high) / 2; /* 折半  */
        if (key < a[mid]) {
            high = mid - 1;
        }
        else if (key > a[mid]) {
            low = mid + 1;
        }
        else
            return mid;
    }
    return 0;
}

折半查找的效率比顺序查找高,但只适用于有序表,且为顺序存储结构,对线性链表无法进行折半查找。

B.斐波那契查找:根据斐波那契序列的特点对表进行分割
举例:有9个元素的数组array对应的斐波那契数列(长度先随便取,只要最大数大于9即可){1, 1, 2, 3, 5, 8, 13, 21, 34},发现大于9且最接近9的斐波那契数值是F[6] = 13,之后将数值array扩充到长度为13,末尾添加的扩充元素为原数值最后一个元素的值。mid的取值与折半查找一样,公式从(low + hig) / 2改为low + (F[k - 1] - 1)。
为什么要把数值长度阔成到F[k] - 1呢?
斐波那契的数组满足:f[k] - 1 = (f[k - 1] + f[k - 2]) - 1,这个- 1的1就是mid,如果目标在左区,数组长度缩短到f[k - 1] ,如果在右区,数组长度缩短到f[k - 2]) - 1,同样f[k - 1]) - 1 = (f[k - 2] + f[k - 3]) - 1,是一个递归的分割。
算法:

static int FibonacciSearch(int [] a, int n, int key) {
    int [] F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
    int low, high, mid, i, k;
    low = 1;
    high = n;
    k = 0;
    while (n > F[k]-1)  {/* 计算n位于斐波那契数列的位置 */
        k++;
    }
    while (low <= high) {
        mid = low + F[k-1] -1;
        if (key < a[mid]){
            high = mid - 1;
            k = k - 1;
        }
        else if (key > a[mid]) {
            low = mid + 1;
            k = k - 2;
        }
        else {
            if (mid <= n)
                return mid;
            else
                return n;
        }
    }
    return 0;
}

斐波那契查找的平均性能比折半查找好,但最坏情况下的性能却比折半查找差,但是分割时只需进行加、减运算。

C.插值查找:根据给定值K来确定比较的关键字r[i].key的查找方法。
打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。
同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。
经过以上分析,折半查找这种查找方式,还是有改进空间的,并不一定是折半的。

折半的
image.png

j将这个1 / 2进行改进,成为
image.png

改成这样有什么道理呢?假设a[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99},low = 1,high = 10,则a[low] = 1,a[high] = 99,如果我们要找的是key = 16时,按原来的折半查找的做法,我们需要四次才可以得到结果,但如果使用新办法,
image.png

即mid ≈ 1 + 0.153*(10 - 1) = 2.377取整得到mid = 2,我们只需要两次查找到结果了,显著大大提高了查找的效率。
换句话说,我们只需要在折半查找算法更改一行代码就可以实现插值算法了。

mid=low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值

插值查找适用于关键字均匀分布的表,在这种情况下,对n值较大的顺序表,他的平均性能比折半查找好。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,921评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,635评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,393评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,836评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,833评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,685评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,043评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,694评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,671评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,424评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,027评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2 343

推荐阅读更多精彩内容