第七章：查找

主关键字：可唯一标识记录的关键字
次关键字：用以识别若干记录的关键字
关键字的平均比较次数，平均查找长度ASL（Average Search Length）

$$
ASL = \sum_{i=1}^np_ic_i
$$

参数	说明
n	记录的个数
p_i	查找到第i个记录的概率
c_i	查找到第i个记录所需的比较次数

一、线性表的查找

1.顺序查找

应用范围：顺序表或线性表表示的静态查找表（表内元素无序）

typedef struct {
    ElemType *R;//表基址
    int length;//表长
} SSTable;//Sequential Search Table
SSTable ST;//定义顺序表ST

注意到每执行一次循环都要进行两次比较，

改进：==利用哨兵简化减少for循环比较次数==，将待查关键字key存入表头，可免去查找过程中每一步都要检测是否查找完毕（加快速度）

注意：当ST.length比较大时，此改进能使进行一次查找所需要的平均时间几乎减少一半。

顺序查找法优点：算法简单，逻辑次序无要求，且不同存储结构均适用

顺序查找法缺点：ASL太长时间效率太低

2.折半查找

折半查找每次可将待查找记录所在的区间缩小一半，

low、hight、mid分别指向待查找元素所在区间的上届、下界和中点，key为给定需要查找的值：
使key与mid值做比较
若key = R[mid]查找成功

若key < R[mid]，则high = mid - 1

若key > R[mid]，则low = mid + 1
重复上述操作，直至low > high查找失败

非递归二叉查找：

int binSearch(SqList sql, int target) {
    int low = 0;
    int high = sql.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        cout << "low : " << low << " high : " << high << " mid : " << mid << endl;
        if (target == sql.elem[mid]) {
            return mid;
        } else if (target < sql.elem[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

递归二分查找：

//low = 0; high = sql.length - 1;
int binSearch(SqList sql, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (target == sql.elem[mid]) {
        return mid;
    } else if (target < sql.elem[mid]) {
        high = mid - 1;
        binSearch(sql, target, low, high);
    } else {
        low = mid + 1;
        binSearch(sql, target, low, high);
    }
}

3.折半查找分析

利用判定树对折半查找进行算法效率分析：

平均查找长度ASL（成功时）：

设表长为n = 2^h - 1，则h = log2(n + 1)其中树为深度为h的满二叉树，且表中每个记录的查找概率相等P_i = 1/n

折半查找优点：效率比顺序查找更高

折半查找缺点：只适用于有序表，且仅限于顺序存储结构（对线性链表无效）

4.分块查找

查找条件：

将表分成若干块，且表或者有序或者分块有序，若i < j则第j块中所有记录的关键字均大于第i块中的最大关键字
建立索引表（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）

查找过程：先确定待查找记录所在块（顺序查找or折半查找），再在块内查找（顺序查找）

查找效率：
$$
ALS = L_b + L_w
$$

参数	说明
L_b	对索引表查找的ASL
L_w	对块内查找的ASL

分块查找法优点：插入和删除比较容易，无需移动大量元素

分块查找法缺点：要增加一个索引表的存储空间，并对初始索引表进行排序运算

分块查找法适用情况：线性表既要快速查找又经常动态变化，则可采用分块查找

二、树表的查找

当表插入删除操作频繁时，为维护表的有序性需要移动表中的很多记录，

可以改用动态查找表（表结构在查找过程中动态生成）几种特殊的树进行优化：

1.二叉排序树BST

（1）基本概念：

二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树，二叉排序树满足：

若左子树非空，则左子树上所有的结点的值均小于根节点的值
若右子树非空，则右子树上所有的结点的值均大于等于根节点的值
其左右子树本身又各是一棵二叉排序树

==二叉排序树的性质==：

中序遍历非空的二叉排序树，所得到的数据元素序列是一个按关键字排列的递增有序序列。

（2）二叉排序树查找：

查找的关键字等于根节点查找成功，否则
若小于根节点，查其左子树
若大于根节点，查其右子树

typedef struct {
    KeyType key;//关键字项
    InfoType otherInfo;//其他数据域
}

typedef struct BSTNode {
    ElemType data;//数据域
    struct BSTNode *lchild, *rchild;//左右孩子指针
} BSTNode, *BSTree;

BSTree T;//定义二叉排序树T