查找: 查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或记录)

查找概论

• 查找表 是由同一类型的数据元素(或记录)构成的集合
• 关键字 是数据元素中某个数据项的值
• 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)
• 对于可以识别多个数据元素(或记录)的关键字，我们称为次关键字
• 静态查找表： 只作查找操作的查找表
• 动态查找表： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

顺序表查找

• 顺序表查找算法
  顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录

/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a, int n, int key){
    for(int i=1; i<=n; i++){
        if (a[i] == key)
            return i;
    }
    return 0;
}

• 顺序表查找优化
  上述顺序表查找并不完美，因为每次循环时都需要对 i 是否越界，即是否小于等于 n 作判断。事实上，可以有更好的办法，设置一个哨兵，可以解决不需要每次让 i 与 n 作比较

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key){
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key){
        i--;
    }
    return i;
}

此时代码从尾部开始查找，由于 a[0]=key ，也就是说，如果在 a[i] 中有 key 则返回 i 值，查找成功，否则一定在最终的 a[0] 处等于 key ，此时返回的是 0 ，即说明 a[1] - a[n] 中没有关键字 key ，查找失败。
这种在查找方向的尽头设置 "哨兵" 免去了在查找过程中每一次比较厚都要判断查找位置是否越界的小技巧，看似已原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，“哨兵” 也不一定就一定要在数据开始，也可以在末端
时间复杂度分析： 对于顺序表来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为 O(1)，最坏情况是在最后一位置找到，需要 n 次比较，时间复杂度为 O(n) ，当查找不成功时，需要 n+1 次比较，时间复杂度为 O(n)。我们之前推导过，关键字在任何一位置都是相同的，所以平均查找次数为 (n+1)/2 ，所以最终时间复杂度为O(n)

有序表查找

• 折半查找
  折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键字有序（通常从小到大有序），线性表必须采用顺序存储。
  折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止
  折半查找时间复杂度为 O(log₂n)；最好是一次找到，最差是下图
  

/* 折半查找 */
int Binary_Search(int *a, int n, int key){
    int low, high, mid;
    low = 1;    /* 定义最低下标为记录首位 */
    high = n;   /* 定义最高下标为记录末位 */
    while(low <= high){
        mid = (low + high) / 2; /* 折半 */
        if (key < a[mid])       /* 若查找值比中值小 */
            high = mid-1;       /* 最高下标调整到中位下标小一位 */
        else if (key > a[mid])/* 若查找值比中值大 */
            low = mid + 1;      /* 最低下标调整到中位下标大一位 */
        else
            return mid;     /* 若相等则说明mid即为查找到的位置 */
    }
    return 0;
}

• 插值查找
  插值查找是二分查找的优化，在数据关键字分布均匀较为合适，反之不是很合适选择
  适当了解即可
• 裴波那契查找
  不做要求

线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程。一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术
索引按照机构可以分为线性索引，树形索引和多级索引。我们这个只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种索引技术：稠密索引，倒排索引，分块索引

• 稠密索引
  是指在线性索引中，将数据集中的每个记录对应一个索引项
  

  稠密索引对应的东西可能是成千上万条数据，因此，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列

• 分块索引
  

  稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数

• 倒排索引
  倒排索引源于实际应用中需要根据属性(或字段。次关键码)的值来查找记录。
  这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。
  由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引

二叉排序树

平衡二叉树(AVL树)

平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1
我们将二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF( Balance Factor)，那么平衡二叉树上所有节点的平衡因子只可能是 -1，0，1。只要二叉树上有一个节点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的

• 原理
  距离插入节点最近的，且平衡因子的绝对值大于 1 的节点为根的子树，我们称为最小不平衡子树。如下图，当新插入节点 37 时，距离它最近的平衡因子绝对值超过 1 的节点是 58 (即它的左子树高度 2 减去右子树高度 0)，所以从 58 开始一下的子树为最小不平衡子树
  平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树各节点之间的链接关系，进行相应的旋转，使之称为新的平衡子树
• 实现算法 (暂时不考虑)

多路查找树 (B树)

• 2-3 树
• 2-3-4 树
• B树
• B+树

散列表查找(哈希表)概论

• 查找定义
  散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。
  这里我们把这种对应关系 f 称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们成为散列地址

• 查找步骤
  散列表最适合的求解问题是查找与给定值相等的记录。但是不适合一个关键字对应多个纪录的情况，也不适合范围查找

散列函数的构造方法

构造原则： 计算简单，散列地址分布均匀

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 除留余数法
• 随机数法

处理散列冲突的方法

• 开放定址法
• 再散列函数法
• 链地址法
• 公共溢出区法

散列表查找实现

• 散列表查找算法实现
• 散列表查找性能优化