搜索算法
2025年2月26日大约 5 分钟
搜索算法是算法领域中非常重要的一部分，解决如何高效地查找目标数据或在特定规则下找到符合条件的解。在许多场景中，如路径规划、AI 搜索、数据查询等，搜索算法发挥着重要作用。
目录
1. 搜索算法简介
搜索算法是一类用于在数据结构（如数组、链表、树、图等）上快速查找目标数据或解的算法。核心问题是如何高效找到目标并降低时间复杂度。
2. 搜索算法分类
根据应用领域和需求，搜索算法可以分为如下主要类别：
| 分类 | 描述 | 代表算法 |
|---|---|---|
| 基本搜索算法 | 在数组或列表中查找数据 | 线性搜索、二分搜索 |
| 图搜索算法 | 遍历图中所有节点或找到数据 | DFS、BFS |
| 启发式搜索算法 | 基于启发式策略寻找最优解 | A* 算法、Dijkstra |
| 哈希搜索/散列搜索 | 基于哈希表快速查找 | 哈希表搜索 |
3. 基本搜索算法
3.1 线性搜索 (Linear Search)
原理
逐个遍历数组的每个元素并检查是否有匹配的值。如果找到则返回索引；若未找到返回 -1。
特性
- 时间复杂度：(O(n))
- 优点：适用于无序列表。
- 缺点：不高效。
Java 实现
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // 找到目标返回索引
}
}
return -1; // 未找到目标
}
public static void main(String[] args) {
int[] arr = {4, 2, 8, 1, 9};
int target = 8;
int result = linearSearch(arr, target);
System.out.println("结果索引: " + result);
}
}3.2 二分搜索 (Binary Search)
原理
在有序数组中通过不断将搜索范围缩小为一半来查找数据。
特性
- 时间复杂度：(O(\log n))
- 优点：适用于有序数组，效率高。
- 缺点：要求数组必须预先排序。
Java 实现
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 避免溢出
if (arr[mid] == target) {
return mid; // 找到目标返回索引
} else if (arr[mid] < target) {
low = mid + 1; // 继续搜索右半部分
} else {
high = mid - 1; // 继续搜索左半部分
}
}
return -1; // 未找到目标
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 5;
int result = binarySearch(arr, target);
System.out.println("结果索引: " + result);
}
}4. 图搜索算法
4.1 深度优先搜索 (Depth-First Search, DFS)
原理
从一个节点开始沿某一条路径尽可能深地搜索，然后回溯并继续搜索其他路径。常用递归或栈实现。
特性
- 时间复杂度：(O(V + E))（V 是节点数，E 是边数）
- 空间复杂度：递归实现需要栈空间。
- 优点：实现简单，适合搜索路径问题。
- 缺点：容易陷入死循环（需要标记访问状态）。
Java 实现
import java.util.*;
public class DFS {
public static void depthFirstSearch(Map<Integer, List<Integer>> graph, int start, boolean[] visited) {
visited[start] = true; // 标记当前节点已访问
System.out.print(start + " "); // 打印节点
for (int neighbor : graph.get(start)) {
if (!visited[neighbor]) {
depthFirstSearch(graph, neighbor, visited); // 递归处理未访问节点
}
}
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3, 4));
graph.put(2, Arrays.asList(0, 5, 6));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(1));
graph.put(5, Arrays.asList(2));
graph.put(6, Arrays.asList(2));
boolean[] visited = new boolean[7];
depthFirstSearch(graph, 0, visited); // 从节点 0 开始 DFS
}
}4.2 广度优先搜索 (Breadth-First Search, BFS)
原理
从起始节点逐层向外扩展，直到找到目标节点或遍历完整个图。通常使用队列实现。
特性
- 时间复杂度：(O(V + E))
- 空间复杂度：需要队列存储节点。
- 优点：适合最短路径问题。
- 缺点：需要额外的空间（队列）。
Java 实现
import java.util.*;
public class BFS {
public static void breadthFirstSearch(Map<Integer, List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true; // 标记起始节点
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " "); // 打印节点
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true; // 标记已访问
queue.add(neighbor); // 将邻居加入队列
}
}
}
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3, 4));
graph.put(2, Arrays.asList(0, 5, 6));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(1));
graph.put(5, Arrays.asList(2));
graph.put(6, Arrays.asList(2));
breadthFirstSearch(graph, 0); // 从节点 0 开始 BFS
}
}5. 启发式搜索算法
5.1 A* 搜索算法 (A* Search)
- A*（A-Star）搜索结合代价函数和启发函数，通常用于路径规划。
- 启发式算法适合复杂图和路径问题。
6. 搜索算法比较
| 搜索算法 | 适用场景 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|---|
| 线性搜索 | 无序数组 | (O(n)) | (O(1)) | 简单但效率低 |
| 二分搜索 | 有序数组 | (O(\log n)) | (O(1)) | 高效，但需有序数据 |
| DFS | 图或树的深度搜索 | (O(V + E)) | (O(V)) | 適合路径问题 |
| BFS | 图或树的广度遍历 | (O(V + E)) | (O(V)) | 适合最短路径问题 |
7. 总结
本文总结了搜索算法的基本理论、分类、特点以及 Java 实现代码。不同搜索算法适合不同场景，理解其适用性和特点是高效求解问题的关键。