前言

“查找”学习提纲（一）——线性查找

代码模板

查找的基本概念

相关概念

  • 查找：在数据集合中寻找满足某种条件的数据元素的过程
  • 查找表：同一类型的数据元素的集合
  • 记录：数据元素
  • 关键字：唯一标识数据元素的数据项/字段的值

查找（表）的类型

  • 静态查找（表）
  • 动态查找（表）

查找的相关操作

  • 判断是否存在——静态
  • 检索各种属性——静态
  • 插入——动态
  • 删除——动态

查找的结果

  • 成功
  • 失败

查找方式的选择因素

  • 查找表的数据结构：如顺序存储或链式存储
  • 查找表中关键字的次序：如无序或有序

查找的性能分析

时间复杂度->平均查找长度（ASL）/平均比较次数：

  • 查找长度/比较次数：比较关键字的次数
  • 平均查找长度（ASL）：查找每记录的概率（一般为1/n）×查找长度。n为数据规模

空间复杂度

顺序/线性查找

适用

  • 线性表

注意：有序线性表的顺序查找和有序顺序表的折半查找，思想不同

性能

平均查找长度（ASL）：

  • 查找成功：(n+1)/2。n为数据规模
  • 查找失败：n或n+1（使用哨兵机制）

时间复杂度：O(n)

空间复杂度：O(1)。未使用额外辅助空间

有序表查找失败的平均查找长度（ASL）：n/2+n/(n+1)。其他相同

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//顺序/线性查找 无序
//适用：
//线性表
//注意：有序线性表的顺序查找和有序顺序表的折半查找，思想不同
//平均查找长度（ASL）：
//查找成功：(n+1)/2。n为数据规模
//查找失败：n或n+1（使用哨兵机制）
//时间复杂度：O(n)
//空间复杂度：O(1)。未使用额外辅助空间
//有序表查找失败的平均查找长度（ASL）：n/2+n/(n+1)。其他相同
int seqSearch(const vector<ELEM_TYPE> &sTable, ELEM_TYPE sKey) //参数：查找表，需查找的关键字
{
    for (int i = 0; i < sTable.size(); ++i) //循环遍历
    {
        if (sTable[i] == sKey) //查找成功
        {
            return i;
        }
    }

    return -1; //查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//顺序/线性查找 无序    使用“哨兵”机制
int seqSearch2(vector<ELEM_TYPE> &sTable2, ELEM_TYPE sKey) //参数：查找表，需查找的关键字
{
    //约定：第一个位置为哨兵
    sTable2[0] = sKey; //设置哨兵

    int i = sTable2.size() - 1; //循环变量
    while (sTable2[i] != sKey)  //循环遍历    每循环只比较1次而不是2次
    {
        --i;
    }

    return i; //查找成功或查找失败
}

折半/二分查找

适用

  • 有序顺序表

性能

平均查找长度（ASL）：[log以2为底的(n+1)]-1。n为数据规模

时间复杂度：O(logn)

空间复杂度：O(1)。未使用额外辅助空间

代码模板

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
//折半/二分查找
//适用：
//有序顺序表
//平均查找长度（ASL）：[log以2为底的(n+1)]-1。n为数据规模
//时间复杂度：O(logn)
//空间复杂度：O(1)。未使用额外辅助空间
int binSearch(const vector<ELEM_TYPE> &sTable, ELEM_TYPE sKey) //参数：查找表，需查找的关键字
{
    //约定：
    //采用递增/升序排序
    //循环不变量原则：左闭右闭为有效区间

    int left = 0;                  //左位置的指针
    int right = sTable.size() - 1; //右位置的指针

    while (left <= right) //当左位置的指针<=右位置的指针时，循环
    {
        int mid = (left + right) / 2; //中间位置的指针  注意：下取整
        //int mid = left + (right - left) / 2; 

        if (sTable[mid] == sKey) //查找成功
        {
            return mid;
        }
        else if (sTable[mid] > sKey) //中间位置的的值比需查找的关键字大
        {
            right = mid - 1; //在左半边区间查找
        }
        else if (sTable[mid] < sKey) //中间位置的的值比需查找的关键字小
        {
            left = mid + 1; //在左半边区间查找
        }
    }

    return -1; //查找失败
}

插值查找

适用

  • 有序顺序表

性能

时间复杂度：O(logn)。n为数据规模

空间复杂度：O(1)。未使用额外辅助空间

若数据规模大，关键字分布均匀，则性能优于折半查找

代码模板

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
//插值查找
//适用：
//有序顺序表
//时间复杂度：O(logn)。n为数据规模
//空间复杂度：O(1)。未使用额外辅助空间
//若数据规模大，关键字分布均匀，则性能优于折半查找
int insSearch(const vector<ELEM_TYPE> &sTable, ELEM_TYPE sKey) //参数：查找表，需查找的关键字
{
    //约定：
    //采用递增/升序排序
    //循环不变量原则：左闭右闭为有效区间

    int left = 0;                  //左位置的指针
    int right = sTable.size() - 1; //右位置的指针

    while (left <= right) //当左位置的指针<=右位置的指针时，循环
    {
        int mid = left + (right - left) * (sKey - sTable[left]) / (sTable[right] - sTable[left]); //插值位置的指针  注意：下取整
        //与折半查找唯一不同的地方
        //折半查找：int mid = left + (right - left) / 2;
        //插值公式：(sKey - sTable[left]) / (sTable[right] - sTable[left])
        //核心思想：依据需要查找的值动态确定区间的缩减幅度
        //若(sKey - sTable[left]) / (sTable[right] - sTable[left])大，则mid大
        //即：在区间范围内，需要查找的值与左边界相对差大，则插值位置应靠右
        //若(sKey - sTable[left]) / (sTable[right] - sTable[left])小，则mid小
        //即：在区间范围内，需要查找的值与左边界相对差小，则插值位置应靠左

        if (sTable[mid] == sKey) //查找成功
        {
            return mid;
        }
        else if (sTable[mid] > sKey) //插值位置的的值比需查找的关键字大
        {
            right = mid - 1; //在左半边区间查找
        }
        else if (sTable[mid] < sKey) //插值位置的的值比需查找的关键字小
        {
            left = mid + 1; //在左半边区间查找
        }
    }

    return -1; //查找失败
}

斐波那契查找

适用

  • 有序顺序表

性能

时间复杂度：O(logn)。n为数据规模

空间复杂度：

  • O(1)。未使用额外辅助空间（不包括斐波那契数列的大小）
  • O(m)。m为斐波那契数列的大小（包括斐波那契数列的大小）

通常性能优于折半查找

代码模板

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//斐波那契查找
//适用：
//有序顺序表
//时间复杂度：O(logn)。n为数据规模
//空间复杂度：O(n)。n为斐波那契数列的大小
//通常性能优于折半查找
//核心思想
// 1.创建大小合适的斐波那契数列
// 2.获取基准斐波那契数的下标：基准斐波那契数-1刚好>=查找表的大小
// 3.如果查找表的大小<基准斐波那契数-1：查找时，分隔值的下标对查找表可能越界，需要扩充查找表
// 4.查找
int fibSearch(vector<ELEM_TYPE> &sTable3, ELEM_TYPE sKey) //参数：查找表，需查找的关键字
{
    // 1.创建大小合适的斐波那契数列
    //大小合适：
    //依据第2步：获取基准斐波那契数的下标：基准斐波那契数-1刚好>=查找表的大小
    //即：斐波那契数列中，存在一个斐波那契数，该斐波那契数-1>=查找表的大小
    //若:
    //查找表的大小为1，查找表 = {2}
    //斐波那契数列大小为1，斐波那契数列 = {0}
    //有0 - 1 < 2，不满足条件
    //若:
    //查找表的大小为1，查找表 = {2}
    //斐波那契数列大小为5，斐波那契数列 = {0,1,1,2,3}
    //有3 - 1 >= 2，满足条件
    vector<int> f(10, 0); //大小合适，初始化为0

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i < 10; ++i)
    {
        f[i] = f[i - 2] + f[i - 1];
    }

    //输出斐波那契数列
    cout << "斐波那契数列：";
    for (int num : f)
    {
        cout << num << " ";
    }
    cout << endl;

    // 2.获取基准斐波那契数的下标：基准斐波那契数-1刚好>=查找表的大小
    int index = 0; //斐波那契数的下标

    // while (f[index] - 1 < sTable3.size()) //会判断为false跳过循环，导致错误
    // while (f[index] < sTable3.size()) //无错误
    int tmp = sTable3.size(); //临时变量存储查找表的大小
    while (f[index] - 1 < tmp)
    {
        ++index;
    }

    //输出基准斐波那契数的下标
    cout << "基准斐波那契数的下标：" << index << endl;

    // 3.如果查找表的大小<基准斐波那契数-1：查找时，分隔值的下标对查找表可能越界，需要扩充查找表
    // 扩充查找表的大小=基准斐波那契数-1
    //理由：统一格式，方便循环或者递归的编写
    //由斐波那契数列的性质：f[index - 2] + f[index - 1] = f[index]
    //总共有f[index] -  1个元素
    // mid为下标有1个元素
    //剩余f[index] - 2个元素：f[index] - 2 = (f[index - 2] - 1) + (f[index - 1] - 1)
    //左区间有f[index - 1] - 1个元素
    //右区间有f[index - 2] - 1个元素
    //左、右区间元素个数的格式与之前统一
    //否则有可能是f[index - 2]、f[index - 2] - 1、f[index - 1]、f[index - 1] - 1
    //查找表中，下标为原查找表大小到斐波那契数-1-1的值=下标为原查找表大小-1的查找表值 即扩充值=原查找表最右边的值

    //验证：
    //斐波那契数列 = {0,1,1,2,3,5,8,13,21,34}
    //查找表 = {1,2,3,4,5,6,7,8,9,10,10,10}
    //第一次循环：
    // index = 7
    // f[index - 1] = f[6] = 8
    // f[index - 1] - 1 = f[6] - 1 = 8 - 1 = 7
    // left = 0
    // mid = left +  f[index - 1] - 1 = 0 + 7 = 7   注意：针对下标
    //分隔值：sTable[7] = 8
    //左区间 = {1,2,3,4,5,6,7}  有f[index - 1] - 1 = 7个元素
    //右区间 = {9,10,10,10} 有f[index - 2] - 1 = f[5] - 1 = 5- 1 = 4个元素
    //以此类推
    int oldSize = sTable3.size(); //记录原查找表的大小 在第4步需要使用

    if (sTable3.size() < f[index])
    {
        //查找表中，下标为原查找表大小到斐波那契数 - 1 - 1的值=下标为原查找表大小-1的查找表值 即扩充值=原查找表最右边的值
        //斐波那契数 - 1：针对大小
        //斐波那契数 - 1 - 1：针对下标
        for (int i = sTable3.size(); i < f[index] - 1 - 1; ++i)
        {
            sTable3.push_back(sTable3[sTable3.size() - 1]); //注意：sTable3.size()+1
        }
    }

    //输出查找表
    cout << "查找表：";
    for (ELEM_TYPE num : sTable3)
    {
        cout << num << " ";
    }
    cout << endl;

    // 4.查找
    //约定：
    //采用递增/升序排序
    //循环不变量原则：左闭右闭为有效区间

    int left = 0;                   //左位置的指针
    int right = sTable3.size() - 1; //右位置的指针

    //测试案例：sKey>10，如=11时，left和mid不变，index不断-1，<0无效时仍进入循环导致错误
    while (left <= right && index >= 0) //当左位置的指针<=右位置的指针且基准斐波那契数的下标有效时，循环
    {
        //见第3步的解析
        //左区间有f[index - 1] - 1个元素
        //分隔值的元素是第f[index - 1] - 1 + 1个
        //因为下标从0开始，所以分隔值的位置：f[index - 1] - 1
        int mid = left + f[index - 1] - 1; //分隔值位置的指针

        if (sTable3[mid] == sKey) //查找成功
        {
            if (mid < oldSize) // oldSize针对下标 分隔值位置的指针<原查找表的大小，对原查找表未越界
            {
                return mid; //分隔值位置的指针即查找位置
            }
            else //分隔值位置的指针>=原查找表的大小，对原查找表越界
            {
                //在第3步：扩充值=原查找表最右边的值
                //对原查找表越界的位置/扩充值查找成功->对原查找表最右边的值查找成功
                //原查找表最右边的值的下标即查找位置
                return oldSize - 1;
            }
        }
        else if (sTable3[mid] > sKey) //分隔值位置的的值比需查找的关键字大
        {
            right = mid - 1; //在左半边区间查找

            index = index - 1; //更新基准斐波那契数的下标
        }
        else if (sTable3[mid] < sKey) //分隔值位置的的值比需查找的关键字小
        {
            left = mid + 1; //在左半边区间查找

            index = index - 2; //更新基准斐波那契数的下标
        }
        //见第3步解析
        //左区间有f[index - 1] - 1个元素    更新基准斐波那契数的下标-1
        //右区间有f[index - 2] - 1个元素    更新基准斐波那契数的下标-2
    }

    return -1; //查找失败
}

折半、插值和斐波那契查找总结

  • 过程相似
  • 分隔值的选择策略不同

索引查找的类型

  • 线性索引
  • 树形索引
  • 多级索引

线性索引的类型

  • 稠密索引：一个索引对应一条记录；记录可无序，索引有序；索引是主关键字
  • 分块索引：一个索引对应多条记录/一个块；块内可无序，块间有序；索引是主关键字
  • 倒排索引：一个索引对应多条记录；记录可无序，索引有序；索引是次关键字

分块/索引顺序查找

适用

  • 线性表

结构描述

查找表：

  • 块内可无序
  • 块间有序：前一个块中的最大关键字小于后一个块中的所有关键字，以此类推

索引表：索引块，有序

  • 键值分量：各块的最大关键字
  • 链值分量：各块的第一条记录的地址/指针
  • …。如块中记录的个数等

算法描述

  1. 对块间/索引表：顺序查找或折半查找等
  2. 对块内/查找表：一般为顺序查找，若有序可为折半查找等

性能

平均查找长度（ASL）：ASL1 + ASL2。其中ASL1为对块间查找的平均查找长度（ASL），ASL2为对块内顺序查找的平均查找长度（ASL）

时间复杂度：O(logn)~O(n)。n为数据规模

  • O(logn)。n为数据规模（对块间折半查找等+对块内顺序查找）
  • O(n)。n为数据规模（对块间顺序查找+对块内顺序查找）

空间复杂度：

  • O(1)。未使用额外辅助空间（不包括索引表的大小）
  • O(m)。m为索引表的大小（包括索引表的大小）

查找表的大小为n，块数为b，每块中的记录数为s，等概率情况：

  • 对块间顺序查找，对块内顺序查找：ASL = ASL1 + ASL2 = (b + 1)/2 + (s + 1)/2 = (s² + 2 × s + n)/(2 × s）
  • 对块间顺序查找，对块内顺序查找，b = s = 根号n：ASL = 根号n + 1
  • 对块间折半查找，对块内顺序查找：ASL = ASL1 + ASL2 = [log以2为底的b]下取整+1或[log以2为底的(b + 1)]上取整 + (s + 1)/2
  • b = s = 根号n，ASL为最小/优值

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//结构体
//定义
//分块查找中，索引表元素
typedef struct IndexElem
{
    ELEM_TYPE maxKey; //键值分量：各块的最大关键字
    ELEM_TYPE first;  //链值分量：各块的第一条记录的地址/指针
} IndexElem;
// struct IndexElem：结构体数据类型的名称
//如创建一个索引表元素的语句：struct IndexElem elem;
//若结构体数据类型内，存在指向该结构体的指针数据类型，则必须完整命名结构体数据类型的名称
//如索引表元素结构体IndexElem内，若存在指向该结构体的指针数据类型，则命名语句为：typedef struct IndexElem而不是typedef struct
// }IndexElem;：typedef给结构体数据类型起的别名，可简化语句
//如创建一个索引表元素的语句：IndexElem elem;
//结构体数据类型的名称和别名尽量一致，以方便记忆、使用

struct IndexElem indexTable[10]; //创建索引表

总结

名称 适用 时间复杂度 空间复杂度
顺序查找 线性表 O(n) O(1)
折半查找 有序顺序表 O(logn) O(1)
插值查找 有序顺序表 O(logn) O(1)
斐波那契查找 有序顺序表 O(logn) O(m)
稠密索引查找 - - -
分块查找 线性表 O(logn)~O(n) O(m)
倒排索引查找 - - -

参考资料

作者的话

  • 感谢参考资料的作者/博主
  • 作者：夜悊
  • 版权所有，转载请注明出处，谢谢~
  • 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
  • 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
  • 文章在认识上有错误的地方, 敬请批评指正
  • 望读者们都能有所收获