第 2 章. 搜索算法
推荐阅读：【算法】【算法目录】(https://jb243.github.io/pages/1278)
1. 概述
2. 线性搜索
4. 其他搜索算法
a. 【搜索算法实验】(https://jb243.github.io/pages/1964)
1.概述
⑴ 搜索
① 给定一个数组 C = ｛a1, a2, ···, an｝ 和一个键 e，查找 ai 其中 ai = e 的过程
② 第一个满足上述条件的元素
③ 或 ，满足上述条件的最后一个元素
④ 或 ，满足上述条件的所有元素
⑵ 数组C可以是已排序数组，也可以是未排序数组
① Linear search: O(N)
② 二分查找：O(log2 N)
③ 排序后查找一次：O(N log2 N) + O(log2 N) = O(N log2 N)
④ 排序后N次搜索：O(N log2 N) + N × O(log2 N) = O(N log2 N)
⑤ 对已排序数组进行 N 次搜索：N × O(log2 N) = O(N log2 N)
⑶ 类型
① Type 1. Depth-First Search (DFS)
○ 基于堆栈
○ 内存使用：O(D) 或 O(D × B)（其中 D = 最大深度，B = 分支因子）
○ Does not always find the shortest path
受保护_0
② 类型2. 广度优先搜索（BFS）
○ 基于队列
○ 内存使用：O(BD)（其中 D = 最大深度，B = 分支因子）
○ 总是找到最短路径
受保护_1
2.线性搜索
⑴ 概述
① 逐一检查每个元素以查看特定元素是否存在的方法
② 可用于已排序和未排序的数组
③时间复杂度
⑵ 算法（Python）
①返回是否找到元素的线性搜索算法
受保护_2
② 线性搜索算法，返回找到的元素的位置
受保护_3
③ Linear search algorithm for a sorted array
受保护_4
3.二分查找
⑴ 概述
① 二分查找需要有序数组
⑵ 二叉树
①定义：由度数为2或以下的节点组成的树，意味着节点最多可以有两个子节点
② 二叉树第 i 层节点的最大数量为 2i-1
③ 类型1. 满二叉树：完全填充的树
④ 类型2. 完全二叉树：只有最后一片叶子未完全填充的树
⑤ 类型3. 倾斜二叉树：一种特殊的二叉树，其中节点只有左或右子节点
⑶ 检索原理
给定一个像 4, 6, 5, 3, 7, 2 这样的序列，让我们构建一个二叉树，如下所示。
首先，附加 4 作为根。那么6大于4，所以它附着在4的右边。接下来，5大于4，所以它沿着6的方向，但由于它小于6，所以它附着在6的左边。树就是这样构建的。对于每个节点的名称，两个直接相连的节点中距离根较近的节点称为父节点，距离根较远的节点称为兄弟节点。另外，兄弟节点分为左兄弟节点和右兄弟节点。此外，如果存在从一个节点到另一个节点的路径，则前者称为祖先节点，后者称为后代节点。> 将二叉树中的每个节点用二进制表示，可以更方便地进行各种操作。每个替代值定义如下：
然后4变成1，3变成10，6变成11，5变成110。
在二叉树中查找特定值的过程称为二叉树搜索或二叉树遍历。二叉树搜索有四种类型： 首先，中序遍历按照左、中、右的顺序搜索，得到2-3-4-5-6-7。当输出正在搜索的节点的顺序时，树中的节点值被排序。其次，层序遍历按照最小级别（距根的最短距离）的顺序搜索节点，并遵循 4-3-6-2-5-7 的顺序。第三，前序遍历按照中心、左、右的顺序搜索，得到4-3-2-6-5-7。最后，后序遍历按照左、右、中的顺序进行搜索，得到2-3-5-7-6-4。二叉树搜索通常使用递归函数来实现。例如，中序遍历可以实现为 f(4) = f(3) + 4 + f(6)。
现在让我介绍一下级别祖先（LA）操作。 LA(x, k) 表示值为 x 的节点的第 k 层祖先节点的值。例如，LA(2, 1) = 3，LA(5, 3) = -1。这里，-1 是一个例外值，当您指定比给定节点更高的级别时，该值始终出现。使用替代值可以轻松计算此操作。
这里的log值是x - 1的替代值的位数。这个值很容易计算出来。
另一种操作是最低共同祖先 (LCA)。 LCA(x,y)表示值为x和y的节点中最接近的共同祖先节点（即具有最高级别的节点）的值。例如，LCA(5, 7) = 6，LCA(2, 6) = 4。这也可以使用替代值来计算。
还有各种其他运算，也可以使用替代值进行计算。这表明创造性的方法如何能够显着简化复杂的问题。
⑷ 算法（Python）
① 使用递归的算法
受保护_5
② 使用迭代的算法
受保护_6
4.其他搜索算法
⑴ 类型1. Elastic Search：Google使用的自然语言搜索算法
输入：2016.09.18 21:47