Python数据结构之搜索讲解

搜索的定义

搜索是在数据集合中查找特定目标的过程。在计算机科学中，最常见的搜索是在数据结构中查找某个特定值的过程。常见的搜索算法包括线性搜索、二分搜索、深度优先搜索和广度优先搜索等。下面我们将详细讲解这些搜索算法的具体实现。

线性搜索

线性搜索是最基本的搜索算法，在一个数据集合中按顺序逐个查找目标值。可以通过以下 Python 代码实现线性搜索：

def linear_search(target, lst):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

其中 target 是要查找的目标值，lst 是数据集合。在上述代码中，我们使用了 for 循环遍历 lst，在每次循环中判断当前元素是否等于 target，如果等于则返回当前下标。如果最终没有找到目标值，则返回 -1，表示搜索失败。

二分搜索

二分搜索又称折半搜索，是一种利用数据集合有序这一特点进行优化的搜索算法。它的基本思想是将数据集合分成两部分，每次查找先判断目标值与中间值的大小关系，从而确定下一次查找的数据集合。可以通过以下 Python 代码实现二分搜索：

def binary_search(target, lst):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] < target:
            low = mid + 1
        elif lst[mid] > target:
            high = mid - 1
        else:
            return mid
     return -1

其中 target 是要查找的目标值，lst 是有序数据集合。在上述代码中，我们首先将要查找的数据集合的范围初始化为整个 lst。然后在 while 循环中，每次查找都将数据集合分成两部分。如果中间值小于目标值，则说明目标值应该在右半部分，更新数据集合范围为右半部分。如果中间值大于目标值，则说明目标值应该在左半部分，更新数据集合范围为左半部分。如果中间值等于目标值，则说明已经找到目标值，返回中间值下标。如果最终没有找到目标值，则返回 -1，表示搜索失败。

深度优先搜索

深度优先搜索是一种利用栈实现的搜索算法，它的基本思想是先访问顶点，然后依次访问与它相邻的未被访问过的顶点，直至搜索到目标值或者无法继续搜索为止。可以通过以下 Python 代码实现深度优先搜索：

def dfs(graph, start, target):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        if node == target:
            return True
        stack.extend(graph[node] - visited)
    return False

其中 graph 是表示图的字典，start 是搜索的起始顶点，target 是要查找的目标值。在上述代码中，我们使用栈来实现深度优先搜索，将起始顶点加入栈中。对于每个出栈的顶点，我们首先判断该顶点是否已经被访问过。如果已经被访问过，则继续出栈下一个顶点；如果未被访问过，则将该顶点标记为已访问。如果该顶点等于目标值，则搜索成功，返回 True。否则，将该顶点的未访问邻居加入栈中，继续搜索下一个顶点。如果最终没有找到目标值，则返回 False，表示搜索失败。

广度优先搜索

广度优先搜索是一种利用队列实现的搜索算法，它的基本思想是先访问距离起始顶点最近的顶点，然后依次访问距离起始顶点更远的顶点，直至搜索到目标值或者无法继续搜索为止。可以通过以下 Python 代码实现广度优先搜索：

def bfs(graph, start, target):
    queue = [start]
    visited = set()
    while queue:
        node = queue.pop(0)
        if node in visited:
            continue
        visited.add(node)
        if node == target:
            return True
        queue.extend(graph[node] - visited)
    return False

其中 graph 是表示图的字典，start 是搜索的起始顶点，target 是要查找的目标值。在上述代码中，我们使用队列来实现广度优先搜索，将起始顶点加入队列中。对于每个出队列的顶点，我们首先判断该顶点是否已经被访问过。如果已经被访问过，则继续出队列下一个顶点；如果未被访问过，则将该顶点标记为已访问。如果该顶点等于目标值，则搜索成功，返回 True。否则，将该顶点的未访问邻居加入队列中，继续搜索下一个顶点。如果最终没有找到目标值，则返回 False，表示搜索失败。

示例说明

示例一

假设我们要在一个无序数组中查找目标值 8，可以使用线性搜索算法，其中 lst=[1, 3, 5, 8, 2, 4, 7, 9]，代码如下：

print(linear_search(8, [1, 3, 5, 8, 2, 4, 7, 9]))

这段代码将返回 3，表示在给定的数组中找到了目标值 8，并且它的下标为 3。

示例二

假设我们要在一个有序数组中查找目标值 6，可以使用二分搜索算法，其中 lst=[1, 2, 3, 4, 5, 6, 7, 8, 9]，代码如下：

print(binary_search(6, [1, 2, 3, 4, 5, 6, 7, 8, 9]))

这段代码将返回 5，表示在给定的有序数组中找到了目标值 6，并且它的下标为 5。

以上便是 Python 数据结构之搜索讲解的完整攻略。