1、查找算法
常见的查找算法
1、顺序查找
2、折半查找（二分查找）
3、索引顺序查找（分块查找）
4、树表查找
5、哈希查找
查找表及查找效率
• 查找表定义：是指由同一类型的数据元素（或记录）构成的集合。
• 静态查找表：只进行“查询”和“检索”操作。
• 动态查找表：除了查询和检索外可能还会进行插入和删除操作。
• 关键字：是数据元素(或记录)的某个数据项的值，用它来识别(标识)这个数据元素(或记录)。
• 查找：根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。
• 平均查找长度(ASL)：对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较” 。因此，通常以“其关键字和给定值进行比较的记录个数的平均值”作为衡量查找算法好坏的依据。
1、顺序查找
从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
7 14 3 10 6 12 1 15 9 13 2 5 8 4 11
• 查找效率低，但是算法简单且适应面广。
2、折半查找(二分查找)
• 基本思想：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（查找不成功）为止。
• 这种方法要求查找表进行顺序存储并且按关键字有序排列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
• 查找效率比顺序查找要高，但要求关键字有序排列。
• 适用于表不易变动，且又经常进行查找的情况。
3、折半查找断定树
• 从折半查找的过程来看，可以用一棵二叉树来描述。通常称这个描述折半查找二叉树的过程称为折半查找判定树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4、树表查找
• 二叉查找树是一种动态查找表，表结构本身是在查找过程中动态生成的。
• 设关键字序列为{46，25，54，13，29，91}
5、索引顺序查找(分块查找)
• 是对顺序查找的一种改进
• 将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的。
6、哈希查找
• 前面几种查找方法中，记录的存储位置和关键码之间不存在确定的关系，因此查找时都要建立在对关键字进行比较的基础之上。
• 哈希函数：关键字作为自变量，关键字存放的地址作为因变量。
Hi=Hash(Key)
• 这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。