暴力搜索

【概述】

顺序查找（Sequential search），又称线性查找，其可分为无序表的查找和有序表的查找

对无序表的查找即暴力搜索，其核心思想是：将所有情况都列举到线性表或数组中，根据要求找一个合适的维度，枚举每一个元素，并对每一个元素判断其是否符合条件

在编程实现上，暴力搜索枚举的内容需要已知，不能在枚举到某个地方的时候出现未知

一般主流的 OJ 中，1000ms 的时间限制下可以运行操作数为 10^7 以内的运算（10^6 以内较保险），所以在采用枚举方法之前最好看一下数据范围，确保整个程序的执行操作数不会超过 10^6~10^7 量级

【模板】

int search(int a[], int n) { //对长度为n的数组a进行暴力搜索
    for (int i = 0; i < n ;i++) {
        if (a[i] 满足某个条件)
            return a[i]
    }
}

【平均查找长度】

对于含有 $n$ 个元素的查找表，假设枚举到第 $i$ 个元素时，与所给的关键字相同，即需要进行 $n-i+1$ 次关键字的比较

那么，查找成功时，平均查找长度为：

$$ASL=\sum_{i=1}^nP_i\cdot(n-i+1)$$

当每个元素的查找概率相等时，有：

$$ASL_{成功}=\sum_{i=1}^n \frac{1}{n}\cdot(n-i+1)=\frac{n+1}{2}$$

而查找不成功，说明从表首枚举到表尾无一元素与关键字匹配，此时与表中各关键字的比较次数显然是 $n+1$ 次

那么，查找不成功时的平均查找长度为：

$$ASL_{失败}=n+1$$