数据结构篇：常用查找算法回顾

（一）基本概念

1. 查找

def 在数据集合中寻找满满足某种条件的数据元素的过程

2. 查找表

def 用于查找的数据集合，由同一类型数据元素组成
操作
- 查（是否有某元素、特定数据结构的某属性）
- 插（同类型某数据元素）
- 删（同类型某数据元素）
分类
- 静态查找表：顺序查找、折半查找和散列查找
- 动态查找表：二叉排序树（二叉平衡树、B 树）的查找、散列查找

3. 关键字

def 数据元素中唯一标识该元素的某数据项的值
method 使用关键字查找，结果唯一

4. 平均查找长度 average search length

def 所有查找过程中进行进行关键字比较次数的平均值
- quiz 衡量查找算法效率用什么指标？ASL
公式令 n 为查找表长度， $P_i = \frac{1}{n}$ 为查找第 i 个数据元素的概率， $c_i$ 为找到第 i 个数据元素的比较次数

$ASL = \sum_{i=1}^{n}{P_iC_i}$

（二）线性表查找

1. 顺序查找 / 线性查找

typedef int ElemType;
typedef struct {
    ElemType* elem; // base
    int tableLen;   // length
} SSTable;

int searchSeq(SSTable ST, ElemType key) {
    ST.elem[0] = key; // set sentinel at index 0
    int i;
    for (i = ST.tableLen; ST.elem[i] != key; i--);

    return i;
}

method 对含 n 个元素的表，定位第 i 个元素，需比较 n-i+1 次（注意为从后往前，严蔚敏版）

$ASL_{success} = \sum_{i=1}^{n} P_i (n-i+1) = \frac {n+1}{2}(P_i = \frac {1}{n} 时)$

$ASL_{fail} = n + 1$
优点对数据元素的存储无要求（顺序、链式均可）
缺点 n 较大 - ASL 较大，效率低
时间复杂度 $O(n)$
优化
- quiz1 针对有序表的情况，有什么区别？
$ASL_{success} = \sum_{i=1}^{n} P_i (n-i+1) = \frac {n+1}{2}(P_i = \frac {1}{n} 时)$

$q_j = \frac{1}{n+1}$ 为到达第 j 个失败结点的概率， $l_j$ 为第 j 个失败结点所在的层数，则 ASL 可优化为：

$ASL_{fail} = \sum_{j=1}^{n}q_j(l_j-1) = \frac{n}{2} + \frac{n}{n+1}$
- quiz2 针对被查概率不相等的情况，又有什么方法？
  
  答：可以将被查概率大的数据元素前置，从降低关键字的比较次数 $C_i$ 入手，降低 ASL

2. 折半查找 / 二分

bool check(int x) {}

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }

    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);
        if (check(mid)) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }

    return l;
}

method 每次找中间位置比较，若与给定 key 相等则成功；大于给定 key 值，则应该在前半部分（升序排列时），反之亦然
- 前提仅适用于有序的顺序表
$ASL_{success} = \frac{1}{n}\sum_{i=1}^{n}l_i = \frac{n+1}{n}log_2(n+1)-1 \approx log_2(n+1)-1$
def 判定树：折半查找形成的二叉树，是一棵平衡二叉树

$树高 h = \lceil log_2 (n+1) \rceil$
优点时间复杂度较降低，为 $O(log_2{n})$
缺点线性表需能随机存储，即仅顺序存储结构适用，且需有序

3. 分块查找

method 在索引表中确定待查记录所属的分块（可顺序、可折半），在块内顺序查找
- 特点块内无序块间有序
- 假设长 n 的查找表被均匀分为 b 块，每块 s 个元素，设索引查找和块内查找的平均查找长度分别为 $L_I$ $L_{I}$ 、 $L_S$ $L_{S}$ ，则分块查找的平均查找长度为 $ASL=L_I + L_S$ $A S L = L_{I} + L_{S}$
  - 顺序查找： $L_I = \frac{1+2+...+b}{b} = \frac{b+1}{2},L_S = \frac{s+1}{s}$ ； $ASL=\frac{s^2+2s+n}{2s}$ ，当 $s = \sqrt{n}$ 时， $ASL_{min} = \sqrt{n+1}$
  - 折半查找： $L_I =\lceil log_2(b+1) \rceil,L_S = \frac{s+1}{s}$ ； $ASL=\lceil log_2(b+1) \rceil + \frac{s+1}{2}$

（三）树表查找

1. 二叉排序树 BST

// Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
}TreeNode, * BinaryTree;

// search
TreeNode* searchBST(BinaryTree T, int val) {
    while (T != NULL && val != T->val)
        T = val < T->val ? T->left : T->right;
    
    return T;
}

val 左＜根＜右
时间复杂度 $O(log_2n)$ ：n 个结点的二叉树最小高度为 $\lfloor log_2n \rfloor+1$ ，时间复杂度最好 $O(log_2n)$ ，最坏 $O(n)$

2. 平衡二叉树 AVL

def 树上任一结点的左子树和右子树的高度之差不超过 1
假设以 $n_h$ 表示深度为 h 的平衡树中含有的最少结点数，则 $n_0 = 0, n_1 = 1, n_2 = 2$ ，且 $n_h = n_{h−1} + n_{h−2} + 1$
时间复杂度 $O(log_2n)$

3. 多路平衡查找树 B 树

def 一棵 m 阶 B 树是所有结点孩子个数的最大值为 m 的多路平衡查找树
- m 叉查找树中，除根节点的其他结点至少有⌈m/2⌉个分叉，⌈m/2⌉ − 1 个关键字
- 对任意结点，其所有子树高度均相同
method m 叉查找树
高度（不含叶结点，此时搜索失败） $log_m(n + 1) ≤ h ≤ log_{⌈m/2⌉}\frac{ n + 1 }{2} + 1$

B + 树

def 结点的子树个数 = 关键字个数，分支结点值 = 子树中关键字的最大值，相邻叶结点按大小链接
method 多级分块查找
支持顺序查找，查找稳定

（四）散列表

def
- 同义词：关键字通过散列函数映射到同⼀个值
- 冲突：散列函数确定的位置已存放其他元素；降低冲突，才能提高查找效率
- 装填因子： $α = \frac {表中记录数}{散列表长度}$
时间复杂度：同时取决于散列函数、处理策略和装填因子，最好情况下复杂度为 $O(1)$
散列函数
- 除留余数法： $H(key) = key \% p$ （p 是不大于散列表长的质数）
- 直接定址法： $H(key) = key$ / $H(key) = a*key + b$
- 数字分析法：取数码分布较均匀的若干位
- 平方取中法：取关键字平方值的中间几位

（1）开放地址法

$H_i = (H(key) + d_i) \% m$

def 空闲地址既向它的同义词表项开放，⼜向它的非同义词表项开放
冲突处理线性探测法（逐个试探后移）平方探测法（skip 后移）伪随机序列法

（2）链地址法

def 链表存储同义词

（3）* 再散列法

def 使用多个散列函数；当散列函数冲突时，⽤下一个散列函数计算