目录
基本概念
查找表：由同一类型的数据元素构成的集合。
关键字：用来标识一个数据元素的某项数据的值? ?主关键字 、次关键字
查找成功：给出记录信息或位置 、 查找不成功：给出空记录或空指针
平均查找长度ASL（Average Search Length) 期望值
查找的操作：
- 查询某个特定的数据元素是否在表中。（静态查找表）
- 检索某个特定的数据元素的各种属性。（静态查找表）
- 在查找表中插入一个数据元素。（动态查找表）
- 删除查找表中的某些元素。（动态查找表）
1 线性表的查找
-
顺序查找（线性查找）
应用范围：
- 顺序表或线性链表表示的静态查找表
- 表内元素无序
数据类型定义：
| 数据元素类型定义 | 顺序表的定义 |
顺序查找：?
?从最后一个元素开始查找：
改进：把待查关键字key存入表头（哨兵、监视哨）
设置监视哨的顺序查找：
当ST较大时，改进能使进行一次查找所需平均时间几乎减少一半。
比较次数与key位置有关：
- 查找第i个元素，需要比较n-i+1次
- 查找失败，需比较n+1 次
时间复杂度：
平均查找长度ASL:
空间复杂度：一个辅助空间——O（1）
顺序查找的特点：
- 优点：算法简单，逻辑次序无要求，且不同存储结构均适用。
- 缺点：ASL太长，时间效率低。
-
折半查找（二分或对分查找）
折半查找：每次将待查记录所在区间缩小一半。
mid = (low + high) /? 2? ? ?中间位置的值
key<mid : high = mid -1? ?关键字的值比中间位置的值小
key>mid : high = mid +1? ?关键字的值比中间位置的值大
key == mid? 找到
high < low?? 结束
折半查找算法:（非递归）
- 设表长为n，low、high、mid 分别指向代茶元素所在区间的上界、下界和中点，key为给定的要查找的值
- 初始令? low=1,? high=n,? mid=(low+high)/2
- 让k与mid指向的记录比较
- 重复上述操作，直至high < low，查找失败
折半查找算法:（递归）
判定树
| 查找成功 | 查找不成功 |
| 比较次数 = 路径上的结点数 | 比较次数 = 路径上的内部结点数 |
| 比较次数 = 结点的层数 | 比较次数 = 结点的层数 |
| 比较次数 ≤ 树的深度 = log2n+1 | 比较次数 ≤ 树的深度 = log2n+1 |
平均查找长度ASL 【成功时】
?
时间复杂度：O（logn)
- 折半查找优点：效率比顺序查找高。
- 折半查找缺点：只适用于有序表，且限于顺序存储结构。（对线性链表无效）?
-
分块查找
分块查找（Blocking Search) （索引顺序查找）
- 将表分成几块，且表有序，或者分块有序。
- 建立索引表。（每个结点的最大关键字域和第一个结点的指针，且关键字有序）
- 先确定待查记录所在块（顺序或折半），再在块内查找。
平均查找长度ASL：
?用折半查找确定块的分块查找ASL：
- 优点：插入和删除比较容易，无需进行大量移动。
- 缺点：要增加一个索引表的存储空间，并对初始索引表进行排序运算。
- 使用情况：既要快速查找又经常动态变化的线性表
查找方法比较?
| 顺序查找 | 折半查找 | 分块查找 | |
| ASL | 最大 | 最小 | 中间 |
| 表结构 | 有序表 | 有序表 | 分块有序 |
| 存储结构 | 顺序表、线性链表 | 顺序表 | 顺序表、线性链表 |
?
2 树表的查找
-
二叉排序树
-
平衡二叉树
-
B-树
-
B+树