搜索算法

搜索算法是用于在数据集合中查找特定项或元素的方法或过程。这些算法在计算机科学中广泛使用，对于在数据库中搜索特定记录、在排序列表中查找元素或在计算机上定位文件等任务至关重要。

以下是一些常用的搜索算法

1. 线性搜索：在这种简单的算法中，会顺序检查集合中的每个元素，直到找到所需项或遍历整个列表。它适用于小型或未排序的列表，但在最坏情况下的时间复杂度为 O(n)。
2. 二分搜索：此算法仅适用于已排序的列表。它重复将列表的中间元素与目标元素进行比较，并根据比较结果将搜索范围缩小一半。二分搜索的时间复杂度为 O(log n)，这使得它对于大型已排序列表非常高效。
3. 哈希：哈希算法使用哈希函数将搜索键转换为数组的索引或地址（称为哈希表）。如果哈希函数分布良好并且冲突处理得当，这允许以常数时间检索所需项。常见的哈希技术包括直接寻址、独立链和开放寻址。
4. 插值搜索：与二分搜索类似，插值搜索适用于已排序的列表。插值搜索不是始终将搜索范围一分为二，而是使用目标元素的值和端点的值来估计其在列表中的大致位置。此估计有助于快速缩小搜索空间。如果数据均匀分布，插值搜索的平均时间复杂度通常为 O(log log n)。
5. 基于树的搜索：各种树数据结构，例如二叉搜索树 (BST)、AVL 树或 B 树，可用于高效搜索。这些结构对元素施加了排序，并提供了快速搜索、插入和删除操作。基于树的搜索算法的时间复杂度取决于树的高度，在最坏情况下可以从 O(log n) 到 O(n)。
6. 三分搜索：三分搜索是一种在已排序列表上运行的算法，它根据两个分割点将搜索范围反复分成三部分而不是两部分。它是一种分而治之的方法，时间复杂度为 O(log₃ n)。
7. 跳跃搜索：跳跃搜索是一种针对已排序列表的算法，它通过跳跃固定数量的步骤，然后在缩小的子数组中执行线性搜索来工作。它对于大型已排序数组非常有用，时间复杂度为 O(sqrt(n))，其中 n 是数组的大小。
8. 指数搜索：指数搜索是一种结合了二分搜索和线性搜索元素的的技术。它从一个小的范围开始，然后将搜索范围加倍，直到目标元素位于该范围之内。然后它在该范围内执行二分搜索。当目标元素很可能在数组开头附近找到时，指数搜索具有优势，其时间复杂度为 O(log n)。
9. 斐波那契搜索：斐波那契搜索是一种使用斐波那契数来划分搜索空间的搜索算法。它适用于已排序的数组，其方法与二分搜索类似，但不是将数组分成两半，而是使用斐波那契数作为索引将其分成两部分。斐波那契搜索的时间复杂度为 O(log n)。
10. 树的插值搜索：此算法是插值搜索的扩展，专为树结构（如 AVL 树或红黑树）设计。它将插值搜索原理与树遍历相结合，根据元素的值高效地定位树中的元素。时间复杂度取决于树结构，在最坏情况下可以从 O(log n) 到 O(n)。
11. 基于哈希的搜索（例如，布隆过滤器）：基于哈希的搜索算法利用哈希函数和数据结构（如布隆过滤器）来确定元素是否存在于集合中。这些算法提供概率性答案，这意味着它们偶尔可能会出现误报（指示元素存在但实际上不存在），但不会出现误报（如果元素不存在，它将永远不会声称它存在）。布隆过滤器的搜索操作具有常数时间复杂度。
12. 字符串搜索算法：特定于字符串数据的搜索算法包括 Knuth-Morris-Pratt (KMP) 算法、Boyer-Moore 算法、Rabin-Karp 算法等技术。这些算法优化了文本或字符串中模式的搜索，并广泛用于文本处理、模式匹配和字符串匹配任务。

搜索算法的实现

线性搜索

C++ 代码

输出

The target value 9 is found at index 4.

C 代码

输出

The target value 9 is found at index 4.

说明

1. linearSearch 函数接受三个参数：arr（数组）、size（数组大小）和 target（要搜索的值）。
2. 在 linearSearch 函数内部，for 循环用于遍历数组的每个元素。循环变量 i 初始化为 0，循环继续，只要 i 小于数组的大小。
3. 在循环内部，数组的每个元素都使用表达式 arr[i] == target 与目标值进行比较。如果找到匹配项，函数会立即返回索引 i，指示元素在数组中的位置。
4. 如果循环结束时未找到匹配项，函数返回 -1，表示在数组中未找到目标值。
5. 在 main 函数中，创建并初始化了一个示例数组 myArray。目标值设置为 9。
6. 通过将数组的总大小 (sizeof(myArray)) 除以单个元素的大小 (sizeof(myArray[0])) 来计算数组的大小。这确保将数组的大小正确传递给 linearSearch 函数。
7. linearSearch 函数以数组、大小和目标值作为参数调用。返回值存储在 result 变量中。
8. 如果结果不等于 -1，则表示在数组中找到了目标值。在这种情况下，使用 printf() 打印一条消息，指示找到目标值的索引。
9. 如果结果为 -1，则表示在数组中未找到目标值。在这种情况下，打印一条消息，指示目标值不存在于数组中。
10. 程序通过从 main 函数返回 0 来终止。

二分搜索

递归代码

输出

Element is found at index 1

说明

• binarySearch 函数接受数组、要搜索的元素 (x)、下限索引 (low) 和上限索引 (high) 作为参数。
• 它首先检查 high 是否大于或等于 low。如果不是，则表示未找到元素，并返回 -1。
• 如果 high 大于或等于 low，则它使用公式 low + (high - low) / 2 计算中间索引 mid。
• 然后它检查中间索引处的元素 (array[mid]) 是否等于 x。如果它们相等，则表示找到元素，并返回索引 mid。
• 如果 array[mid] 大于 x，则表示元素位于数组的左半部分。在这种情况下，以 low 不变且 high 设置为 mid - 1 递归调用 binarySearch 函数。
• 如果 array[mid] 小于 x，则表示元素位于数组的右半部分。在这种情况下，以 low 设置为 mid + 1 且 high 不变递归调用 binarySearch 函数。
• 如果在递归调用后未找到元素，函数返回 -1。
• 在 main 函数中，定义了一个数组 {3, 4, 5, 6, 7, 8, 9}，并使用公式 sizeof(array) / sizeof(array[0]) 计算数组的大小 n。
• 要搜索的元素 x 设置为 4。
• binarySearch 函数以数组、x 和索引范围 0 到 n - 1 调用。
• 返回的结果存储在 result 变量中。
• 最后，检查结果。如果为 -1，则表示未找到元素，并打印“未找到”。否则，打印找到元素的索引，例如“在索引结果处找到元素”。

迭代

输出

Element is found at index 1

说明

• binarySearch 函数接受数组、要搜索的元素 (x)、下限索引 (low) 和上限索引 (high) 作为参数。
• 它使用 while 循环，该循环一直持续到低指针小于或等于高指针。
• 在循环内部，它使用公式 low + (high - low) / 2 计算中间索引 mid。
• 然后它检查中间索引处的元素 (array[mid]) 是否等于 x。如果它们相等，则表示找到元素，并返回索引 mid。
• 如果 array[mid] 小于 x，则表示元素位于数组的右半部分。在这种情况下，低指针更新为 mid + 1。
• 如果 array[mid] 大于 x，则表示元素位于数组的左半部分。在这种情况下，高指针更新为 mid - 1。
• 如果循环后未找到元素，则表示数组中不存在该元素，并且函数返回 -1。
• 在 main 函数中，定义了一个数组 {3, 4, 5, 6, 7, 8, 9}，并使用公式 sizeof(array) / sizeof(array[0]) 计算数组的大小 n。
• 要搜索的元素 x 设置为 4。
• binarySearch 函数以数组、x 和索引范围 0 到 n - 1 调用。
• 返回的结果存储在 result 变量中。
• 最后，检查结果。如果为 -1，则表示未找到元素，并打印“未找到”。否则，打印找到元素的索引，例如“在索引结果处找到元素”。

哈希

输出

Value for key 2: 200

说明

1. C 语言实现首先包含必要的头文件：stdio.h 用于标准输入/输出操作，stdlib.h 用于内存分配。
2. 定义了一个常量 TABLE_SIZE 来确定哈希表数组的大小。
3. 定义了一个结构体 Node 来表示键值对。它有三个成员：key、value 和 next。next 成员是指向下一个节点的指针，以防发生冲突。
4. 声明了一个全局变量 table 作为 struct Node* 数组来存储哈希表。
5. hash_function 函数接受一个 key 作为输入，并返回哈希表数组中的索引。它使用模运算符 % 和 TABLE_SIZE 来计算索引。
6. insert 函数接受一个 key 和 value 作为输入。它使用 hash_function 计算索引，并将包含键值对的新节点插入到计算出的索引处的链表中。
7. search 函数接受一个 key 作为输入，如果找到，则返回与哈希表中键关联的值。它使用 hash_function 计算索引，并遍历计算出的索引处的链表以搜索键。
8. main 函数初始化哈希表，向其中插入元素，并执行搜索操作。

Java 代码

输出

Value for key 2: 200

说明

1. Java 实现定义了一个带有键和值字段的 Node 类来表示键值对。
2. HashTable 类封装了哈希表功能。
3. 该类有一个构造函数，它接受哈希表的大小作为输入，并初始化一个空的列表的 ArrayList 来表示桶。
4. hashFunction 方法接受一个键作为输入，并返回哈希表数组中的索引。它使用除法方法（键 % size）来计算索引。
5. insert 方法接受一个键和值作为输入。它使用 hashFunction 计算索引，并将新的 Node 对象插入到计算出的索引处的列表中。
6. search 方法接受一个键作为输入，如果找到，则返回与哈希表中键关联的值。它使用 hashFunction 计算索引，并遍历计算出的索引处的列表以搜索键。
7. main 方法创建一个 HashTable 实例，向其中插入元素，并执行搜索操作。

插值搜索

输出

Element 16 found at index 4

说明

1. 插值搜索算法假定我们有一个按升序排序的输入数组。
2. 该算法由两个变量组成：low，指向数组的第一个索引；high，初始化为数组的最后一个索引。
3. 该算法使用目标值 arr[low] 和 arr[high] 来计算目标元素在数组中的可能位置，其中找到元素的可能性很高。它使用投影公式
   pos = low + (((double) (high - low) / (arr[high] - arr[low])) * (value - arr[low])
   上述公式将 pos 位置计算为较低和较高索引的加权平均值，具体取决于相应数组元素的值。目标是计算目标检测的位置。
4. 然后算法将目标值与 arr[pos] 进行比较以确定下一步
   • 如果 arr[pos] 等于给定目标值，则算法搜索目标元素并返回 pos。
   • 如果 arr[pos] 小于给定目标值，算法不会创建另一个 pos + 1，因为目标值可能位于数组的顶部。
   • 如果 arr[pos] 大于目标值，算法会将 up 更新为 pos - 1，因为目标值可能位于数组的下半部分。
5. 算法重复步骤 3 和 4，直到满足以下条件之一
   在位置 pos 找到目标元素，在这种情况下，算法返回该位置。
   low 值大于 high，表明目标不在系统中。在这种情况下，算法返回 -1，表示未找到元素。
6. 示例中的 main 函数演示了 interpolationSearch 函数的用法。它初始化一个数组、其大小和目标值。然后它调用 interpolationSearch 函数来搜索数组中的目标值。
7. 最后，根据返回的索引，main 函数打印一条相应的消息，指示是否找到目标元素。

Java 代码

输出

Element 16 found at index 4

基于树的搜索

深度优先搜索 (DFS)：DFS 是一种递归搜索技术，它在回溯之前尽可能深入地探索树。对于二叉树，DFS 有三种常见的变体

• 先序遍历：访问当前节点，然后递归访问左子树，最后访问右子树。
• 中序遍历：递归访问左子树，访问当前节点，然后递归访问右子树。在二叉搜索树中，此遍历按升序访问节点。
• 后序遍历：递归访问左子树，然后访问右子树，最后访问当前节点。

广度优先搜索 (BFS)：BFS 逐层探索树，在移动到下一层之前访问所有相同深度的节点。它使用队列数据结构来跟踪要访问的节点。BFS 确保在访问更深层的节点之前访问更接近根的节点。

DFS

输出

Depth-First Traversal (DFS): 1 2 4 5 3

说明

• 包含必要的头文件 stdio.h 和 stdbool.h，它们分别提供输入/输出功能和对布尔值的支持。
• 常量 MAX_NODES 定义为 100，表示二叉树中的最大节点数。此值当前未在代码中使用。
• 结构体 Node 定义为表示二叉树中的节点。它包含一个整数数据来存储节点的值，以及两个指向左右子节点的指针 left 和 right。
• 函数 createNode 是一个实用函数，它接受一个整数数据作为输入，并使用给定数据值创建一个新节点。它使用 malloc 为新节点分配内存，并将 left 和 right 指针初始化为 NULL。函数返回指向新创建节点的指针。
• 函数 DFS 是深度优先搜索的递归实现。它接受指向节点的指针作为输入并执行 DFS 遍历。基本情况是当前节点为 NULL 时，在这种情况下函数简单返回。否则，它通过使用 printf 打印其数据值来处理当前节点。然后，它递归调用左子树 (node->left) 和右子树 (node->right) 上的 DFS。
• 在 main 函数中，创建了一个示例二叉树。使用 createNode 创建根节点，数据值为 1。为根节点创建了两个子节点，数据值分别为 2 和 3。此外，为根节点的左子节点创建了两个子节点，数据值分别为 4 和 5。
• 最后，通过调用 DFS(root) 对从根节点开始的二叉树执行 DFS 遍历。节点的值按深度优先顺序打印。

BFS

输出

Breadth-First Traversal (BFS): 1 2 3 4 5

说明

• 包含必要的头文件 stdio.h 和 stdbool.h，它们分别提供输入/输出功能和对布尔值的支持。
• 常量 MAX_NODES 定义为 100，表示二叉树中的最大节点数。此值用于定义 Queue 结构中的队列大小。
• 结构体 Node 定义为表示二叉树中的节点。它包含一个整数数据来存储节点的值，以及两个指向左右子节点的指针 left 和 right。
• 结构体 Queue 定义为表示将用于 BFS 的队列。它包含一个 Node 指针数组 items 来存储队列中的节点，以及两个整数 front 和 rear 来跟踪队列的前后索引。
• 函数 createNode 是一个实用函数，它接受一个整数数据作为输入，并使用给定数据值创建一个新节点。它使用 malloc 为新节点分配内存，并将 left 和 right 指针初始化为 NULL。函数返回指向新创建节点的指针。
• 函数 createQueue 通过为 Queue 结构分配内存并将 front 和 rear 索引初始化为 -1 来创建一个空队列。
• 函数 isEmpty 通过检查 rear 索引是否为 -1 来检查队列是否为空。如果是，函数返回 true，表示队列为空。
• 函数 enqueue 将节点添加到队列中。它首先检查队列是否已满（rear 索引等于 MAX_NODES - 1）。如果是，它会打印“Queue Overflow!”消息并返回。否则，它会增加 rear 索引，将节点添加到新 rear 索引处的 items 数组中，并更新 front 索引（如果它为 -1，表示队列为空）。
• 函数 dequeue 从队列中移除并返回一个节点。它首先通过调用 isEmpty 检查队列是否为空。如果队列为空，它会打印“Queue Underflow!”消息并返回 NULL。否则，它会从 front 索引检索节点，增加 front 索引，并检查 front 索引是否已超过 rear 索引。如果是，它会将 front 和 rear 索引都设置为 -1，表示队列为空。最后，它返回出队的节点。
• 函数 BFS 是广度优先搜索的迭代实现。它接受指向二叉树根节点的指针作为输入。它首先使用 createQueue 创建一个队列并使根节点入队。然后，它进入一个循环，在该循环中，它从队列中出队一个节点，通过使用 printf 打印其数据值来处理该节点，并使其左右子节点（如果存在）入队。循环继续，直到队列变空，即没有更多节点需要处理。
• 在 main 函数中，创建了一个示例二叉树。使用 createNode 创建根节点，数据值为 1。为根节点创建了两个子节点，数据值分别为 2 和 3。此外，为根节点的左子节点创建了两个子节点，数据值分别为 4 和 5。
• 最后，通过调用 BFS(root) 对从根节点开始的二叉树执行 BFS 遍历。节点的值按广度优先顺序打印。

三分搜索

输出

Element found at index 5.

说明

• 在此示例中，我们有一个包含一些元素的数组 arr，并且我们想搜索一个键值（在本例中为 23）。ternarySearch 函数接受数组、当前段的左右索引以及要搜索的键。
• 该函数递归地将数组分成三段：mid1 = left + (right - left) / 3 和 mid2 = right - (right - left) / 3。它检查键是否等于 arr[mid1] 或 arr[mid2]。如果任一条件为真，它将返回相应的索引。
• 如果键小于 arr[mid1]，则该函数在左段（left 到 mid1 - 1）上递归。如果键大于 arr[mid2]，则该函数在右段（mid2 + 1 到 right）上递归。否则，如果键在 arr[mid1] 和 arr[mid2] 之间，则该函数在中间段（mid1 + 1 到 mid2 - 1）上递归。
• 如果函数在数组中找不到键，则返回 -1。main 函数使用适当的参数调用 ternarySearch 并相应地显示结果。

指数搜索

输出

Element found at index 5.

说明

• 我们有一个包含一些元素的数组 arr，并且我们想搜索一个键值（在本例中为 23）。exponentialSearch 函数接受数组、数组大小以及要搜索的键。
• 该函数首先检查键是否存在于索引 0 处。如果存在，它立即返回 0。否则，它通过将索引 i 加倍来确定二分搜索的范围，直到达到数组末尾或 arr[i] 变得大于键。
• 确定范围后，该函数调用 binarySearch 函数在该范围内执行二分搜索。binarySearch 函数实现标准的二分搜索算法，如果找到键则返回键的索引，否则返回 -1。
• main 函数使用适当的参数调用 exponentialSearch 并相应地显示结果。

Java 代码

输出

Element found at index 4

说明

1. exponentialSearch 方法接受数组 arr 和目标值 target 作为输入，并返回目标值在数组中的索引。如果未找到目标值，则返回 -1。
2. 该方法首先检查数组的第一个元素 (arr[0]) 是否等于目标值。如果是，则该方法返回 0，因为在第一个索引处找到了目标。
3. 如果未在第一个索引处找到目标值，则该方法继续执行指数搜索算法。它将变量 bound 初始化为 1。此变量表示搜索范围的上限。
4. 然后算法进入一个循环，该循环将 bound 值加倍，直到 bound 超过数组大小 (n) 或 bound 索引处的元素大于目标值。此循环以指数方式缩小搜索范围。
5. 确定 bound 后，该方法调用 binarySearch 方法在确定的搜索范围内执行二分搜索。它将数组、目标值、下限 (bound / 2) 和上限 (Math.min(bound, n - 1)) 传递给 binarySearch 方法。
6. binarySearch 方法是二分搜索算法的递归实现。它接受数组、目标值、左索引和右索引作为参数。
7. 在 binarySearch 方法中，它检查左索引是否大于右索引。如果是，则表示搜索范围内不存在目标值，因此该方法返回 -1。
8. 否则，它将中间索引 (mid) 计算为左右索引的平均值。
9. 然后它将 mid 索引处的元素与目标值进行比较。如果它们相等，则该方法返回 mid 索引，因为找到了目标值。
10. 如果 mid 索引处的元素大于目标值，它会以搜索范围的左半部分（left 到 mid - 1）递归调用 binarySearch 方法。
11. 如果 mid 索引处的元素小于目标值，它会以搜索范围的右半部分（mid + 1 到 right）递归调用 binarySearch 方法。
12. 递归一直持续到找到目标值或搜索范围缩小到左索引大于右索引的点。
13. 在 main 方法中，创建了一个包含排序元素的示例数组 arr。目标值设置为 10。
14. 使用数组 arr 和目标值调用 exponentialSearch 方法。返回的索引存储在 index 变量中。
15. 最后，检查 index 变量。如果它不是 -1，则表示找到了目标值，并显示相应的消息。否则，如果 index 是 -1，则表示未找到目标值，并显示适当的消息。

斐波那契搜索

C 代码

输出

Element found at index 4.

说明

• 首先，fibonacciSearch 函数接受三个参数：一个整数数组 arr、数组大小 n 和要搜索的键元素 key。
• 之后，我们通过初始化三个变量来启动算法：fib2、fib1 和 fib，分别表示第 (m-2) 个、第 (m-1) 个和第 m 个斐波那契数。最初，fib2 设置为 0，fib1 设置为 1，fib 计算为 fib2 和 fib1 的和。
• while 循环用于查找大于或等于 n 的最小斐波那契数。它继续更新 fib2、fib1 和 fib，直到 fib 大于或等于 n。
• 找到斐波那契数后，算法将 offset 变量初始化为 -1。此变量将用于标记从前面消除的范围。
• 算法的主要部分是使用斐波那契数的基于比较的搜索。while 循环一直持续到 fib 变为 1。
• 在循环内部，算法检查 fib2 是否是有效索引。如果 offset + fib2 在数组边界内 (offset + fib2 < n)，则将 offset + fib2 分配给变量 i。否则，将 n - 1 分配给 i。
• 如果键元素大于索引 i 处的值，则表示键很可能在索引 i 之后的子数组中找到。在这种情况下，算法通过更新 fib、fib1、fib2 和 offset 来切断从前面消除的范围。
• 如果键元素小于索引 i 处的值，则表示键很可能在索引 i 之前的子数组中找到。在这种情况下，算法通过更新 fib、fib1 和 fib2 来切断从末尾消除的范围。
• 如果键元素在索引 i 处找到，算法立即返回该索引。
• 如果循环结束时未找到键，算法会执行最终检查。它将消除范围的最后一个元素 (arr[offset + 1]) 与键进行比较。如果它们匹配，算法返回 offset + 1。
• 如果在数组中未找到键元素，算法返回 -1。
• 在 main 函数中，显示了 fibonacciSearch 函数的示例用法。它创建一个数组，定义大小，并设置要搜索的键元素。然后，它调用 fibonacciSearch 函数并打印结果。

Java 代码

输出

Element found at index 4.

说明

• fibonacciSearch 方法接受两个参数：一个整数数组 arr 和要搜索的键元素 key。
• 该算法首先初始化三个变量：fib2、fib1 和 fib，分别表示第 (m-2) 个、第 (m-1) 个和第 m 个斐波那契数。最初，fib2 设置为 0，fib1 设置为 1，fib 计算为 fib2 和 fib1 的和。
• while 循环用于查找大于或等于输入数组 arr 长度的最小斐波那契数。它继续更新 fib2、fib1 和 fib，直到 fib 大于或等于数组长度。
• 找到斐波那契数后，算法将 offset 变量初始化为 -1。此变量将用于标记从前面消除的范围。
• 算法的主要部分是使用斐波那契数的基于比较的搜索。while 循环一直持续到 fib 变为 1。
• 在循环内部，算法计算索引 i 以检查 fib2 是否是有效索引。它取 offset + fib2 和 arr.length - 1 之间的最小值。
• 如果键元素大于索引 i 处的值，则表示键很可能在索引 i 之后的子数组中找到。在这种情况下，算法通过更新 fib、fib1、fib2 和 offset 来切断从前面消除的范围。
• 如果键元素小于索引 i 处的值，则表示键很可能在索引 i 之前的子数组中找到。在这种情况下，算法通过更新 fib、fib1 和 fib2 来切断从末尾消除的范围。
• 如果键元素在索引 i 处找到，算法立即返回该索引。
• 如果循环结束时未找到键，算法会执行最终检查。它将消除范围的最后一个元素 (arr[offset + 1]) 与键进行比较。如果它们匹配，算法返回 offset + 1。
• 如果在数组中未找到键元素，算法返回 -1。
• 在 main 方法中，显示了 fibonacciSearch 方法的示例用法。它创建一个数组，设置要搜索的键元素，调用 fibonacciSearch 方法，并打印结果。

树的插值搜索

输出

Key 30 found in the binary search tree.

说明

• 我们首先包含必要的头文件 stdio.h 和 stdlib.h，它们分别提供输入/输出和内存分配功能。
• 接下来，我们定义一个名为 Node 的结构体来表示二叉搜索树中的节点。该结构体包含一个整数 key 来存储节点的值，以及两个指针 left 和 right 分别指向左右子节点。
• 我们定义一个 createNode 函数，它接受一个键值作为输入，并为新节点动态分配内存。该函数初始化节点的键，并将 left 和 right 指针设置为 NULL。
• insertNode 函数用于将新节点插入到二叉搜索树中。它接受当前根节点和键值作为输入。如果根为 NULL，表示树为空，则该函数使用 createNode 函数创建一个新节点并返回它。否则，它根据键值递归遍历树，将其与当前节点的键进行比较。如果键较小，则移动到左子节点；如果键较大，则移动到右子节点。该函数继续此过程，直到找到适当的位置来插入新节点。
• interpolationSearch 函数在二叉搜索树中执行插值搜索算法。它接受根节点和键值作为输入。该函数检查根节点是否为 NULL，或者键值是否与当前节点的键匹配。如果这些条件中的任何一个为真，则返回当前节点。否则，它将键值与当前节点的键进行比较，并决定是在左子树还是右子树中搜索。它递归调用适当子树上的 interpolationSearch 函数，直到找到键或到达 NULL 节点。
• 在 main 函数中，我们创建一个空的二叉搜索树根，并使用 insertNode 函数插入一些节点。
• 我们定义一个变量 searchKey，其值为 30，这是我们要在二叉搜索树中搜索的键。
• 我们调用 interpolationSearch 函数，以 root 和 searchKey 作为参数。如果返回的结果不为 NULL，则表示在树中找到了键，因此我们打印一条消息，指示找到了键。否则，我们打印一条消息，指示未找到键。

字符串搜索算法

1. 朴素字符串搜索：朴素字符串搜索算法是最基本、最直接的方法。它通过系统地将搜索字符串的每个字符与文本的每个字符进行对比来查找匹配项。该技术的时间复杂度为 O(n*m)，其中 n 是文本长度，m 是搜索字符串的长度。
2. Knuth-Morris-Pratt (KMP) 算法：KMP 算法通过利用先前匹配的数据来防止无意义的比较，从而优于朴素算法。它预先计算一个“前缀函数”或“失败函数”，提供有关搜索字符串中可能匹配的详细信息。KMP 算法的时间复杂度为 O(n+m)，其中 n 是文本长度，m 是搜索字符串长度。
3. Boyer-Moore 算法：Boyer-Moore 方法有效地将搜索字符串与文本从左到右进行比较。它通过使用“坏字符规则”和“好后缀规则”这两个启发式方法，快速移动搜索窗口并跳过比较。Boyer-Moore 算法的平均时间复杂度为 O(n/m)，其中 n 是文本长度，m 是搜索字符串长度。
4. Rabin-Karp 算法通过使用哈希有效地在文本中搜索模式。它在文本上滑动时计算每个窗口的哈希值，同时哈希搜索字符串。如果哈希值匹配，则进行逐字符比较以确认匹配。Rabin-Karp 算法的平均时间为 O(n+m)，其中 n 是文本长度，m 是搜索字符串长度。
5. Aho-Corasick 算法：Aho-Corasick 算法是一种多模式字符串搜索算法，可以同时高效地搜索多个搜索字符串。它构建了一个名为“trie”的有限状态机，用于存储所有搜索字符串。该算法根据输入文本遍历 trie，快速查找所有搜索字符串的出现。Aho-Corasick 算法的时间复杂度为 O(n+m+z)，其中 n 是文本长度，m 是所有搜索字符串的总长度，z 是找到的出现次数。

示例

Boyer-Moore 算法实现

输出

Pattern found at index 4

说明

• 代码首先包含必要的头文件 stdio.h 和 string.h，它们提供输入/输出和字符串操作函数。
• MAX_CHAR 常量定义为 256，表示 ASCII 字符集中支持的最大字符数。
• 定义了 max 函数，它接受两个整数作为输入并返回两者中的最大值。
• 定义了 badCharHeuristic 函数，用于预处理“坏字符”启发式表。此表用于在模式匹配过程中发生不匹配时确定移位。该函数接受模式字符串、其长度和 badChar 数组作为输入。它将 badChar 数组中的所有条目初始化为 -1，然后填充模式中每个字符最后一次出现的实际值。
• search 函数实现 Boyer-Moore 算法进行字符串搜索。它接受文本和模式字符串作为输入。
• 在 search 函数内部，使用 strlen 函数计算文本和模式字符串的长度。
• 声明了 badChar 数组以存储坏字符启发式表。
• 调用 badCharHeuristic 函数以预处理 badChar 表，传入模式、其长度和 badChar 数组。
• shift 变量初始化为 0，表示模式相对于文本的移位。
• 主搜索循环开始。它一直持续到 shift 小于或等于文本长度与模式长度之差。
• 在主搜索循环内部，另一个循环用于从右到左比较模式和文本的字符，从模式末尾开始。它检查匹配，直到找到不匹配或到达模式开头。
• 如果整个模式都匹配（即 j < 0），则找到匹配项，并使用 printf 打印找到模式的索引。然后调整 shift 以通过将文本中的下一个字符与坏字符启发式表进行比较来查找模式的下一个出现。如果存在不匹配，则移动模式以对齐文本中的坏字符。
• 如果在比较循环期间发生不匹配，则根据坏字符启发式调整 shift。max 函数用于计算 1 与当前索引和 badChar 表中不匹配字符最后一次出现的索引之间的差值之间的最大 shift。
• 最后，在 main 函数中演示了一个示例用法。文本变量设置为“ABAAABCD”，模式变量设置为“ABC”。调用 search 函数，并使用这些输入在文本中查找模式的出现。
• 程序通过从 main 函数返回 0 来结束。