def binary_search(arr, target):
    """
    二分查找函数
    
    参数:
    arr (list): 有序的数组
    target (int): 目标值
    
    返回值:
    int: 目标值在数组中的索引，如果不存在则返回-1
    """
    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 = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
print(binary_search(arr, target))  # 输出: 3

target = 14
print(binary_search(arr, target))  # 输出: -1

3
-1

def hash_search(hash_table, key):
    """
    哈希查找函数
    
    参数:
    hash_table (dict): 哈希表，用于存储键值对
    key: 目标键
    
    返回值:
    int: 目标键对应的值，如果不存在则返回None
    """
    if key in hash_table:
        return hash_table[key]
    else:
        return None

# 测试用例
hash_table = {
    'apple': 3,
    'banana': 5,
    'orange': 2,
    'grape': 4
}

key = 'banana'
print(hash_search(hash_table, key))  # 输出: 5

key = 'watermelon'
print(hash_search(hash_table, key))  # 输出: None

5
None

def dfs(graph, start, visited=None):
    """
    深度优先搜索函数
    
    参数:
    graph (dict): 图的邻接表表示，使用字典存储节点和其相邻节点
    start: 开始遍历的节点
    visited (set): 已访问的节点集合
    
    返回值:
    list: 深度优先搜索遍历的节点顺序
    """
    if visited is None:
        visited = set()
    
    visited.add(start)  # 将当前节点标记为已访问
    traversal_order = [start]  # 用于存储遍历的节点顺序
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            traversal_order.extend(dfs(graph, neighbor, visited))  # 递归遍历相邻节点
    
    return traversal_order

# 测试用例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start_node = 'A'
print(dfs(graph, start_node))  # 输出: ['A', 'B', 'D', 'E', 'F', 'C']

start_node = 'D'
print(dfs(graph, start_node))  # 输出: ['D', 'B', 'A', 'C', 'F', 'E']
# 深度优先搜索的时间复杂度为O(V + E)，其中V是节点数，E是边数。
# 在最坏情况下，需要遍历所有的节点和边。空间复杂度为O(V)，由于需要存储已访问的节点集合。
# 请注意，这里的时间复杂度和空间复杂度是针对使用邻接表表示图的情况。
# 如果使用邻接矩阵表示图，时间复杂度和空间复杂度会有所不同。

['A', 'B', 'D', 'E', 'F', 'C']
['D', 'B', 'A', 'C', 'F', 'E']

# 广度优先搜索算法

from collections import deque

def bfs(graph, start, target):
    # 创建一个队列，用于存储待探索的节点
    queue = deque()
    # 将起始节点加入队列
    queue.append(start)
    # 创建一个集合，用于记录已访问的节点
    visited = set()
    # 开始搜索
    while queue:
        # 从队列中取出一个节点
        node = queue.popleft()
        # 如果该节点已访问过，则跳过
        if node in visited:
            continue
        # 将该节点标记为已访问
        visited.add(node)
        # 如果找到了目标节点，返回True
        if node == target:
            return True
        # 将该节点的相邻节点加入队列
        for neighbor in graph[node]:
            queue.append(neighbor)
    # 如果遍历完整个图/树仍未找到目标节点，则返回False
    return False

# 测试用例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A', 'F'))  # 输出: True
print(bfs(graph, 'B', 'C'))  # 输出: True
print(bfs(graph, 'A', 'G'))  # 输出: False
# 复杂度分析：
# 时间复杂度：在最坏情况下，广度优先搜索算法需要遍历图中的所有节点和边。假设图有n个节点和m条边，每个节点最多被访问一次，每个边最多被访问两次（一次作为起始节点的相邻边，一次作为相邻节点的相邻边）。因此，时间复杂度为O(n + m)。
# 空间复杂度：在最坏情况下，广度优先搜索算法需要存储所有待探索的节点和已访问的节点。假设图有n个节点，最坏情况下需要存储n个节点。因此，空间复杂度为O(n)。

True
True
False

# 迪杰斯特拉算法
import sys

def dijkstra(graph, start):
    # 初始化距离字典，将起始节点的距离设为0，其他节点的距离设为无穷大
    distance = {node: sys.maxsize for node in graph}
    distance[start] = 0
    # 创建一个集合，用于记录已访问的节点
    visited = set()
    
    while len(visited) < len(graph):
        # 在未访问的节点中找到距离最小的节点
        min_distance = sys.maxsize
        min_node = None
        for node in graph:
            if node not in visited and distance[node] < min_distance:
                min_distance = distance[node]
                min_node = node
        # 将该节点标记为已访问
        visited.add(min_node)
        if min_node != None:
            print(min_node, graph[min_node])
            # 更新与该节点相邻节点的距离
            for neighbor, weight in graph[min_node].items():
                new_distance = distance[min_node] + weight
                if new_distance < distance[neighbor]:
                    distance[neighbor] = new_distance
    
    return distance

# 测试用例
graph = {
    'A': {'B': 5, 'D': 9, 'E': 2},
    'B': {'C': 2},
    'C': {},
    'D': {'B': 3, 'C': 2}, 
    'E': {'D': 3}
}

print(dijkstra(graph, 'A'))  # 输出: {'A': 0, 'B': 5, 'C': 7, 'D': 8, 'E': 2}
print(dijkstra(graph, 'E'))  # 输出: {'A': inf, 'B': inf, 'C': inf, 'D': 3, 'E': 0}
# 算法复杂度分析：
# 时间复杂度：在最坏情况下，迪杰斯特拉算法需要遍历图中的所有节点和边。假设图有n个节点和m条边，每次在未访问的节点中找到距离最小的节点需要O(n)的时间，更新该节点的相邻节点的距离需要O(m)的时间。因此，总时间复杂度为O(n^2 + m)。
# 空间复杂度：迪杰斯特拉算法需要存储节点的距离和已访问的节点。在最坏情况下，需要存储n个节点的距离和n个已访问的节点。因此，空间复杂度为O(n)。

A {'B': 5, 'D': 9, 'E': 2}
E {'D': 3}
B {'C': 2}
D {'B': 3, 'C': 2}
C {}
{'A': 0, 'B': 5, 'C': 7, 'D': 5, 'E': 2}
E {'D': 3}
D {'B': 3, 'C': 2}
C {}
B {'C': 2}
{'A': 9223372036854775807, 'B': 6, 'C': 5, 'D': 3, 'E': 0}

线性查找¶

二分查找¶

哈希查找¶

图算法¶

深度优先搜索¶

广度优先搜索（BFS）¶

最短路径算法¶