查找（search）：给定结点的关键字值 x ，查找值等于 x 的结点的存储地址。
按关键字 x 查：
① 成功，表中有 x ，返回 x 的存储地址；
② 不成功，x 不在表中，返回无效地址。
顺序查找就是以表的一端为起点，向另一个端点逐个元素查看，
可以是从 表头 → 表尾的顺序，也可以是从 表尾 → 表头的顺序
顺序查找方法，既适用于无序表，又适用于有序表。
顺序查找属于 “穷尽式搜索法”：通常以 查找长度，度量查找算法的时间复杂性。
查找长度：即查找过程中测试的节点数目。
顺序查找的查找长度 = for 循环体的执行次数，最小为1，最多为n。
等概率下：平均查找长度 = （n + 1）/ 2
最坏情况和平均情况：T（n）= O（n） 效率最低的查找算法
我们观察一下上图那两个 for循环体，不难发现，每次执行都需要 判断两个条件：
① 测试是否循环到头；
② 测试是否找到元素 x。
因此我们不妨使用 “监督元” 技术，不仅简化了程序结构，也提高了查找速度。
若从 表尾 → 表头 的顺序查找，监督元则在表头处，称为 “表头监督元”，如下图：
若从 表头 → 表尾 的顺序查找，监督元则在表头处，称为 “表尾监督元”，如下图：
带表头监督元的顺序查找算法：
int SQsearch（int a[]，int x，int n）{ // SQsearch 是函数名，仅此。
int i；
i = n；
a[0] = x；
while（a[i] != x）
i -- ；
return i；
}
算法思想：
① i = n；// 设置查找起点
② a[0] = x；// 放置监督元，因为在进入循环体之前，已经预先在 a[0] 放置了一个元素 x，所以 x 无论是否真的在表中，总能找到 x ，使第三句的循环中止。注意！！！a[1] 到 a[n] 存储的才是真正的表元素。
如果 x 真存在表中，必然在某个 i 大于 0 时找到 x，循环终止。
如果循环变量 i 的值变到 0 时循环才终止，那就说明 x 不在表中。
③ while（a[i] != x）
i --； // 从右向左查。
④ return i；// 判定查找结果。查找结果由变量 i 的值判定，
x 在表中，i ≠ 0
x 不在表中，i = 0
只牺牲一个存储单元，就能将查找效率提升一倍。这在表长 n 较大，查找频繁的情况下是很合算的，“空间换时间”。虽然查找速度提高一倍，但时间复杂性的阶不变，仍是O(n)，只是时间复杂性函数的常系数变小了。
原文：https://www.cnblogs.com/AronKeener/p/14649416.html