2024年回炉计划之搜索算法（二）

????????在计算机科学中，搜索算法是解决搜索问题的任何算法，即检索存储在某个数据结构中的信息，或者在问题域的搜索空间中计算的信息。这种结构的例子包括但不限于链表，数组数据结构或搜索树。合适的搜索算法通常取决于正在搜索的数据结构，并且还可能包括有关数据的先前知识。搜索还包含查询数据结构的算法，例如SQL SELECT命令。

一、分类

????????搜索算法可以根据搜索机制进行分类。线性搜索算法以线性方式检查每个与目标关键字关联的记录。二进制或半间隔搜索，重复定位搜索结构的中心，并将搜索空间分成两半。比较搜索算法通过基于键的比较相继地消除记录来改进线性搜索，直到找到目标记录为止，并且可以按照定义的顺序应用于数据结构。数字搜索算法基于使用数字键的数据结构中的数字属性工作。最后，哈希根据散列函数直接将键映射到记录。在线性搜索之外进行搜索需要以某种方式对数据进行排序。

????????搜索功能也根据其复杂性或最大理论运行时间进行评估。

二、举例

????????以下是一些常见的搜索算法，以及使用 TypeScript 语言的示例：????????

????????线性搜索（Linear Search）:当进行线性搜索时，我们逐个检查数组中的元素，直到找到目标元素或遍历完整个数组。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

function linearSearch<T>(arr: T[], target: T): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // 返回目标元素的索引
        }
    }
    return -1; // 未找到目标元素
}

const array: number[] = [1, 2, 3, 4, 5];
const targetElement: number = 3;
const result: number = linearSearch(array, targetElement);

if (result !== -1) {
    console.log(`元素 ${targetElement} 在数组中的索引为：${result}`);
} else {
    console.log(`未找到元素 ${targetElement} 在数组中`);
}

????????在这个例子中，linearSearch 函数接受一个数组 arr 和一个目标元素 target，然后遍历数组，如果找到目标元素，就返回其索引；否则，返回 -1 表示未找到。最后，根据返回的结果输出相应的信息。

二分搜索（Binary Search）:二分搜索是一种高效的搜索算法，但要求输入数据必须有序

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

function binarySearch<T>(arr: T[], target: T): number {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const midElement = arr[mid];

        if (midElement === target) {
            return mid; // 返回目标元素的索引
        } else if (midElement < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // 未找到目标元素
}

const sortedArray: number[] = [1, 2, 3, 4, 5];
const targetElement: number = 3;
const result: number = binarySearch(sortedArray, targetElement);

if (result !== -1) {
    console.log(`元素 ${targetElement} 在数组中的索引为：${result}`);
} else {
    console.log(`未找到元素 ${targetElement} 在数组中`);
}

在这个例子中，binarySearch 函数接受一个已排序的数组 arr 和一个目标元素 target，然后使用二分搜索算法查找目标元素。如果找到目标元素，就返回其索引；否则，返回 -1 表示未找到。最后，根据返回的结果输出相应的信息。请注意，二分搜索的前提是输入数组必须是有序的。

三、常见的搜索算法

????????常用的搜索算法主要包括线性搜索、二分搜索以及一些基于图和树的搜索算法。以下是一些常见的搜索算法：

1. 线性搜索（Linear Search）:

   • 算法简单，适用于未排序的数据集。
   • 时间复杂度：O(n)

2. 二分搜索（Binary Search）:

   • 仅适用于已排序的数据集，效率高。
   • 时间复杂度：O(log n)

3. 广度优先搜索（Breadth-First Search, BFS）:

   • 用于图的搜索，按层次遍历图中的节点。
   • 适用于无权图或权值相同的图。

4. 深度优先搜索（Depth-First Search, DFS）:

   • 用于图的搜索，沿着图的深度遍历节点。
   • 适用于解决路径问题，如迷宫问题。

5. 哈希表查找（Hash Table Lookup）:

   • 使用哈希函数将键映射到索引，通过索引直接访问数据。
   • 适用于快速查找，平均时间复杂度为 O(1)。

6. A 搜索算法（A-star）:*

   • 用于图和网络的启发式搜索算法，综合考虑启发式评估和已知路径成本。
   • 适用于寻找最短路径。

7. 深度受限搜索（Depth-Limited Search）:

   • 限制深度的深度优先搜索，防止无限制地遍历深度。
   • 适用于避免无限循环的问题。

8. 双向搜索（Bidirectional Search）:

   • 从起点和终点同时开始搜索，当两个搜索相遇时停止。
   • 适用于图搜索中的一些情况，可以减少搜索空间。

这些算法在不同的问题和数据结构中有不同的应用场景。选择合适的搜索算法通常取决于具体问题的特性以及数据集的结构。