搜索算法

搜索算法用于在数据集合中查找特定元素，是计算机科学中的基础算法。

二分查找

概述

二分查找是一种高效的搜索算法，要求数据已经有序排列。

算法步骤

1. 初始化左指针和右指针
2. 计算中间位置
3. 比较中间元素与目标值
4. 根据比较结果调整搜索范围

实现

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 未找到

# 示例
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(arr, target)
print(f"元素 {target} 在索引 {result} 处")  # 元素 23 在索引 5 处

复杂度分析

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

---

深度优先搜索

概述

深度优先搜索（DFS）是一种图遍历算法，沿着一条路径尽可能深地探索，直到到达终点。

算法步骤

1. 访问起始节点
2. 递归访问未访问的相邻节点
3. 回溯到上一个节点继续探索

实现（递归）

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("DFS 遍历结果:")
dfs(graph, 'A')  # A B D E F C

实现（迭代）

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            # 逆序添加以保持顺序
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

print("\nDFS 迭代遍历结果:")
dfs_iterative(graph, 'A')  # A C F E B D

---

广度优先搜索

概述

广度优先搜索（BFS）是一种图遍历算法，按层遍历节点。

算法步骤

1. 访问起始节点
2. 依次访问所有相邻节点
3. 对每个相邻节点重复步骤 2

实现

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# 示例
print("\nBFS 遍历结果:")
bfs(graph, 'A')  # A B C D E F

最短路径

def bfs_shortest_path(graph, start, end):
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # 无路径

# 示例
path = bfs_shortest_path(graph, 'A', 'F')
print(f"\n最短路径: {path}")  # 最短路径: ['A', 'C', 'F']

复杂度分析

• 时间复杂度: O(V + E)，V 为顶点数，E 为边数
• 空间复杂度: O(V)