1.基本概念

查找——在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）——用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。
关键字——数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
1.常见操作

• 1.查找符合条件的数据元素（静态查找表）
• 2.插入，删除某个数据元素（动态查找表）

2.查找算法的评价指标

• 1.查找长度——在查找运算中，需要对比关键字的次数称为查找长度。
• 2.平均查找长度（ASL，Average Search Length）——所有查找过程进行关键字的比较次数的平均值。
  ASL = ∑P_iC_i（i由1->n）
  n为数据元素个数，P为查找第i个元素的概率，C为查找第i个元素的查找长度。
  注：通常认为查找任何一个元素的概率都相同

2.顺序查找

定义：顺序查找又叫线性查找，通常用于线性表（顺序或者链式）。
思想：从头到尾依次查找（顺序或者逆序）
代码实现：

  typedef struct{ // 查找表的数据结构（顺序表）
    int *arr;   // 动态数组基址
    int length; // 表的长度
}SequenceTable;
// 顺序查找
int Search_Seq(SequenceTable ST, int data){
    int i;
    for(i=0; i < ST.length && ST.arr[i] != data; ++i);
    // 查找成功，则返回元素下标；查找失败，则返回-1
    return i==ST.length ? -1 : i;
}

3.折半查找

定义：折半查找也称二分查找，仅适用于有序的顺序表
注：顺序表具有随机访问的特性，链表没有
代码实现：

typedef struct{ // 查找表的数据结构（顺序表）
    int *arr;   // 动态数组基址
    int length; // 表的长度
}SequenceTable;
  // 折半查找(二分查找)
int Binary_Search(SequenceTable ST, int data){
    int low = 0;
    int high = ST.length-1;
    int mid;
    while(low <= high){
        mid = (low + high)/2;   // 取中间位置
        if(ST.arr[mid] == data){
            return mid; // 查找成功则返回所在位置
        }else if(ST.arr[mid] > key){
            high = mid - 1; // 在前半部分继续查找
        }else{
            low = mid + 1;  // 在后半部分继续查找
        }
        return -1;  // 查找失败，返回-1
    }

}

折半查找判定树的构造:

• 1.如果当前low和high之间有奇数个元素，则mid分隔后，左右俩部分元素个数相等。
• 2.如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素。
• 3.折半查找的判定树中，若mid=_┕(low+high)/2_┙，则对于任何一个结点，必有：右子树结点数 - 左子树结点数 = 0或1
• 4.折半查找的判定树一定是平衡二叉树，且只有最下面一层是不满的，因此，元素个数为n时树高h = ^┌log₂(n + 1)^┐
• 5.判定树的结点关键字为左 < 中 < 右，满足二叉排序树的定义，且失败结点为（n+1）个 = 成功结点的空链域数量

4.分快查找

"索引表"中保存每个分快的最大关键字和分块的存储区间。
特点：块内无序，块间有序
思想：分块查找，又称索引顺序查找，算法如下：

• 1.在索引表中确定待查记录所属的分块(可顺序，可二分)
• 2.在快内顺序查找

查找效率分析（ASL）

问题：假设，长度为n的查找表均匀的分为b快，每块s个元素。
解决：设索引查找和快内查找的平均查找长度分别为L_I、L_S，则分块查找的平均查找长度为ASL = L_I+L_S

• 使用顺序查找查索引表，则L_I=(1+2+...+b)/b = (b+1)/2，L_S=(1+2+...+s)/s = (s+1)/2
  则ASL= (b+1)/2+(s+1)/2 = (s²+2s+n)/2s，当s=n^{(1/2)时，ASL取最小值=n}(1/2) + 1