概念章
查找就是在数据集合中寻找某种条件的数据元素的过程。
查找表是指用于查找同一类型的数据元素集合。
找到了满足条件的数据元素，就是查找成功，否则就是称为查找失败。
关键字是指数据元素的某个数据项的值，可用于标识或者记录，一般我们只指一个。
静态查找表是指一个查找表操作仅仅涉及查找操作，简单来说就只是看看，不动态修改查找表。
动态查找表是指对这个查找表的操作设计查找，还要动态的插入和删除查找表。
平均查找长度(Average Search Length)简称为：ASL 是指查找表中每个数据元素需要进行关键字比较次数的平均值。
简单来说，上面的概念都是围绕ASL(平均查找长度)展开的，它的重点也就是两个方面：查找成功和查找失败的平均查找长度。
也就是上面这个公式。
感觉有点模模糊糊的没看太懂？
我们从一道简单的题中来近距离理解平均查找长度的概念。
例子
假设我们有一个有序数组，包含以下元素：
[10, 20, 30, 40, 50]
查找成功的平均查找长度（ASL成功）
假设我们查找的目标是数组中的元素，且每个元素被查找的概率是相等的。
- 查找10：比较1次
- 查找20：比较2次
- 查找30：比较3次
- 查找40：比较4次
- 查找50：比较5次
计算查找成功的平均查找长度（ASL成功）：
[ ASL_{成功} = (1 + 2 + 3 + 4 + 5) / 5 = 15 / 5 = 3 ]
查找失败的平均查找长度（ASL失败）
现在考虑查找一个不在数组中的元素，比如25。为了理解查找失败的平均查找长度，我们需要考虑在查找失败的情况下，需要比较多少次。
对于25，查找过程中会经历：
- 比较10，20，30（3次比较），然后确认25不在数组中。
假设每个元素前后都可能是目标元素，每个元素查找失败的概率也相同。这里我们可以想象在数组的前后各加一个元素（如5和60），以简化计算。
所以失败查找的情况可以如下：
- 查找5：比较1次（确定5小于10）
- 查找15：比较2次（确定15在10和20之间）
- 查找25：比较3次（确定25在20和30之间）
- 查找35：比较4次（确定35在30和40之间）
- 查找45：比较5次（确定45在40和50之间）
- 查找55：比较6次（确定55大于50）
- 查找60：比较6次（确定60大于50）
我们可以假设失败查找有7个情况，每种情况所需的比较次数为：
[ ASL_{失败} = (1 + 2 + 3 + 4 + 5 + 6 + 6) / 7 = 27 / 7 = 3.86(约等于)
概念说完之后，我们来说说最简单的一个查找：顺序查找。
顺序查找
顺序查找又称为线性查找，用于顺序表和链表。
基本思想就是从表头遍历到表尾，直到查找成功或查找失败。
具体来说：
例子
假设我们有一个有序数组，包含以下元素：
[100，1000，8，15，200]，我们要在一个长度为5的顺序表中查找元素8.
顺序查找的源代码如下
#include<stdio.h>
#define MaxSize 100
int SeqSearch(int array[], int n, int key) {for (int i = 0; i < n; i++) {if (array[i] == key) {return i;//查找成功则返回其元素下标}}return -1;//查找失败则返回-1
}int main() {int array[MaxSize] = { 100,1000,8,15,200 };int n = 5;int res = SeqSearch(array, n, 8);printf("查找结果为: %d", res);return 0;
}实现截图：
由此图也可知，代码逻辑没错
同样的，我们也可以将数组元素从下标为1的地方开始存储，然后在下标为0的这里存储待查找的关键字，也可以称为哨兵。
哨兵
将哨兵放在数组头也是一种有效的查找策略，尽管它不如放在尾部常用。使用头部哨兵的主要思路是为了简化查找逻辑。
实现思路
- 设置哨兵：在数组的开头放置一个哨兵值，这个值通常是比数组中所有元素都小（或大）的值。
- 查找过程：从哨兵开始向后查找目标值，直到找到目标值或达到数组的末尾。
优点
- 避免边界检查：因为哨兵在数组的开头，所以在查找过程中不需要检查下标是否小于零。
- 简化逻辑：减少代码中的条件判断，使代码更简洁。
示例
假设我们有数组 [10, 20, 30, 40, 50]，我们在头部添加一个哨兵值（例如，0）：
[0, 10, 20, 30, 40, 50]
查找目标值（例如30）时，过程如下：
- 从哨兵（0）开始，与30比较。
- 继续向后查找，比较10，20，直到找到30。
- 当找到目标时，可以返回目标值的位置，或继续查找直到遇到哨兵。
注意事项
- 使用头部哨兵时，实际查找时需要注意哨兵本身并不代表有效数据，所以在返回结果时需要进行相应处理。
- 哨兵值的选择应确保其不会与数组中的其他元素相同，以避免混淆。
同样的，哨兵也可以放在数组末尾。
哨兵是一种特殊的元素，通常放在数组的末尾，用于避免边界检查。具体来说，当我们查找目标元素时，将目标值与哨兵值进行比较，直到找到目标或到达哨兵。
优点
- 减少比较次数：不需要在每次比较时检查下标是否越界。
- 简化代码：使得代码逻辑更清晰。
示例
假设有数组 [10, 20, 30, 40, 50]，我们在末尾添加一个哨兵值（比如60）：
复制代码
[10, 20, 30, 40, 50, 60]
查找目标值（例如30）时，直接比较目标值和哨兵，直到找到目标或遇到哨兵。
前面我们不是提到了平均查找长度吗，结合顺序查找->
当然，要注意如果查找表的元素是有序的，我们就没必要遍历整个查找表。当发现我们拿到的数据元素比关键字(key)大时，我们就没必要继续往后遍历了。
