常用的7大查找算法之六：分块查找算法（索引顺序查找，一种改进顺序查找）

2017-04-23 18:23 阅读 4,858 次 评论 0 条

1.查找算法概述

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

 

（1）查找定义

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

 

（2）查找算法分类

1）静态查找和动态查找

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

 

（3）查找算法分析

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。

 

2.分块查找

（1）分块查找定义

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

 

（2）算法思想

将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

 

（3）算法流程

第一步：先选取各块中的最大关键字构成一个索引表；
第二步：查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

 

（4）分块查找算法C/C++源代码

分块查找算法C/C++源代码
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
#include <stdio.h>
struct index /*定义块的结构*/
{
    int key;
    int start;
    int end;
} index_table[4]; /*定义结构体数组*/
 
int block_search(int key, int a[]) /*自定义实现分块查找*/
{
        int i, j;
        i = 1;
        while (i <= 3 && key > index_table[i].key) /*确定在那个块中*/
            i++;
        if (i > 3) /*大于分得的块数，则返回0*/
                return 0;
        j = index_table[i].start; /*j等于块范围的起始值*/
        while (j <= index_table[i].end && a[j] != key) /*在确定的块内进行查找*/
                j++;
        if (j > index_table[i].end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/
                j = 0;
        return j;
}
 
main()
{
    int i, j = 0, k, key, a[16];
 
    printf("输入由小到大的15个数:\n");        
    for (i = 1; i < 16; i++)
        scanf("%d", &a[i]); /*输入由小到大的15个数*/
 
    for (i = 1; i <= 3; i++)
     {
            index_table[i].start = j + 1; /*确定每个块范围的起始值*/
            j = j + 1;
            index_table[i].end = j + 4; /*确定每个块范围的结束值*/
            j = j + 4;
            index_table[i].key = a[j]; /*确定每个块范围中元素的最大值*/
     }
 
     printf("输入要查询的数值:\n");
    scanf("%d", &key); /*输入要查询的数值*/
 
    k = block_search(key, a); /*调用函数进行查找*/
 
    if (k != 0)
        printf("success.the position is :%d\n", k); /*如果找到该数，则输出其位置*/
    else
        printf("no found!"); /*若未找到则输出提示信息*/
}

 

（5）分块查找算法C++源代码

分块查找算法C/C++源代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
//分块查找算法
#include <iostream>
using namespace std;
 
//定义一个结构体用来分块
struct index  
{
    int key;
    int start;
    int end;
}index[4];
 
// 分块查找算法
int search (int key,int a[])
{
    int i,j;
    i=0;
    while(i<3&&key>index[i].key)//确定在哪个块中
        i++;
    if(i>=3)//大于分得的块数 返回0
        return -1;
    j=index[i].start;//j等于块范围的起始值
    while(j<=index[i].end&&a[j]!=key)//在确定的块内进行查找
        j++;
    if(j>index[i].end)//如果大于块范围的结束值 则说明没有要查找的数 j置0
        j=-1;
    return j;
}
 
int main()
{
    int i,j=-1,k,key;
    int a[]={42,63,82,89,111,146,219,254,325,336,348,795,867,951,998};
    cout<<"已知有一数组"<<endl;
    for(i=0;i<15;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(i=0;i<3;i++)
    {
        index[i].start=j+1;//确定每个块的起始值
        j=j+1;
        index[i].end=j+4;//确定每个块的结束值
        j=j+4;
        index[i].key=a[j];//确定每个块范围中的元素最大值
    }
    cout<<"请输入你要查找的数："<<endl;
    cin>>key;
    k=search(key,a);
    if(k>=0)
        cout<<"查找成功！你要找的数字在数组中的位置是："<<k+1<<endl;
    else
        cout<<"查找失败！你要找的数字不在数组中。"<<endl;
    return 0;
 
 
}

版权声明：本文著作权归原作者所有，欢迎分享本文，谢谢支持！
转载请注明：常用的7大查找算法之六：分块查找算法（索引顺序查找，一种改进顺序查找） | 算法君
分类：数据结构 标签：, ,

发表评论


表情