查找算法
定义：
- 给定一个值，在大量信息中数据表中确定一个其关键字等于给定值的元素（记录）
查找算法的分类
- 静态查找：在查找过程中不改变数据元素的数据表 --- 不插不删；故采用顺序存储结构
- 动态查找：在查找过程中有插入和删除操作的数据表
- 有序查找：被查找数据表必须为有序序列
- 无序查找：被查找数据表有序无序均可
平均查找长度（Average Search Length，ASL）：
- 需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度，作为衡量查找效率的重要指标。
- 对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci 的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
常见的查找（搜索）算法
- 顺序查找
- 二分查找 (又称为折半查找)
- 分块查找
- 哈希查找（单独）
-
树表查找（在"树"部分详细介绍，本文不重点涉及）
- BST
- BBST
- AVL
- B-Tree
- 红黑树
1. 顺序查找
基本思想 ： 属于无序查找算法，从数据表的一端顺序扫描，依次将数据元素的关键值与给定值Value比较，直至找到相等的表示成功，或扫描结束仍未找到，表示失败；
复杂度分析
- ASL ： 等概率条件下，ASL = (n+....+2+1)/n= (n+1)/2
- 时间复杂度 ： O(n)
代码后补
2. 二分查找（折半查找）
基本思想 ：数据表必须为有序表，属于有序查找算法；如果数据表原本无序，则先要进行排序操作；
给定值为Value，与数据表中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据Value与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归下去，直到查找到或查找结束发现表中没有这样的结点。
[注] 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据表来说，维护有序的排序会带来不小的工作量，不建议使用。
复杂度分析
- ASL ： 在等概率条件下...平均查找长度：ASL =（1/n）* ( j * 2^(j-1) )(j是从1到h)，ASL = log
2(n+1)-1。 - 时间复杂度 ：最坏情况下，关键词比较次数为log
2(n+1)，且期望时间复杂度为O(log2n)；
代码后补
3. 分块查找（也称为索引查找）
分块查找的数据表的特点 ： 分块有序 即[ 块间有序，块内无序]
分块示例
基本思想 ：将一个 n 个数据元素的数据表"按块有序"划分为 m 块(m<=n)，每个块中元素关键字不必有序，但块与块之间必须"按块有序"; 即 第 1 个块中的任一元素的关键字小于第 2 个块中的任一元素的关键字（或大于），第 2 个块中的任一元素的关键字小于第 3 个块中的任一元素的关键字（或大于）... ...
分块算法流程
- 为每一块设立一个块首指针
- 并标注对应块的最大（小）关键字
- 将每一块的块首指针和标注最大关键字合并为一个索引项
- 各个块的索引项一起构成一个索引表
- 查找分为两个部分 ： 先对索引表进行二分或者顺序查找，已确定待查的记录在哪一个块中；然后在已确定的块中进行顺序查找。
代码后补
