穿越搜索迷雾！Python算法解密：线性搜索与二分搜索，助你驾驭搜索之道！

测试开发囤货

发布于 2023-08-08 09:26:50

1710

发布于 2023-08-08 09:26:50

文章被收录于专栏：测试开发囤货

穿越搜索迷雾！Python算法解密：线性搜索与二分搜索，助你驾驭搜索之道！

线性搜索

线性搜索是一种简单的搜索算法，逐个检查列表中的每个元素，直到找到目标元素或遍历完整个列表。

算法步骤：

从列表的第一个元素开始，逐个比较元素与目标元素。
如果找到目标元素，返回其索引。
如果遍历完整个列表仍未找到目标元素，返回-1。

示例

下面是用Python编写的线性搜索算法示例：

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # 如果目标元素不在数组中，返回-1

# 测试示例
nums = [11, 22, 25, 34, 64, 90]
target = 34
index = linear_search(nums, target)
if index != -1:
    print("目标元素", target, "的索引为", index)
else:
    print("目标元素", target, "未找到")

在这个示例中，我们定义了一个函数linear_search，它接受一个列表arr和目标元素target作为输入，并返回目标元素在列表中的索引（如果存在）。

我们使用for循环逐个比较列表中的元素与目标元素，如果找到目标元素，则返回其索引；如果遍历完整个列表仍未找到目标元素，则返回-1。

二分搜索

二分搜索是一种高效的搜索算法，用于在有序列表中查找特定元素的位置。与线性搜索相比，它通过反复将查找范围减半来快速缩小搜索范围。

算法步骤：

确定查找范围的起始点和终点。
计算中间元素的索引。
比较中间元素与目标元素的大小。
如果中间元素等于目标元素，返回其索引。
如果中间元素大于目标元素，更新查找范围的终点为中间元素的前一个位置，回到步骤2。
如果中间元素小于目标元素，更新查找范围的起始点为中间元素的后一个位置，回到步骤2。
重复步骤2到步骤6，直到找到目标元素或查找范围为空。

示例

下面是用Python编写的二分搜索算法示例：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1

    return -1  # 如果目标元素不在数组中，返回-1

# 测试示例
nums = [11, 22, 25, 34, 64, 90]
target = 34
index = binary_search(nums, target)
if index != -1:
    print("目标元素", target, "的索引为", index)
else:
    print("目标元素", target, "未找到")

在这个示例中，我们定义了一个函数binary_search，它接受一个有序列表arr和目标元素target作为输入，并返回目标元素在列表中的索引（如果存在）。

我们使用low和high两个指针来表示查找范围的起始点和终点，然后通过计算中间元素的索引mid来进行比较。根据比较结果，我们更新low和high的值，并重复执行直到找到目标元素或查找范围为空。

可视化

现在让我们通过可视化展示线性搜索和二分搜索算法的执行过程，以加深对算法的理解。

以下是线性搜索的可视化示例：

目标元素: 34
列表: [11, 22, 25, 34, 64, 90]
查找索引: 0   1   2   3    4    5

当前索引: 0，元素: 11，不匹配
当前索引: 1，元素: 22，不匹配
当前索引: 2，元素: 25，不匹配
当前索引: 3，元素: 34，匹配

以下是二分搜索的可视化示例：

目标元素: 34
列表: [11, 22, 25, 34, 64, 90]
查找索引: 0   1   2   3    4    5

查找范围: 0 - 5，中间元素索引: 2，元素: 25
目标元素大于中间元素，更新查找范围为: 3 - 5

查找范围: 3 - 5，中间元素索引: 4，元素: 64
目标元素小于中间元素，更新查找范围为: 3 - 3

查找范围: 3 - 3，中间元素索引: 3，元素: 34
目标元素等于中间元素，找到目标元素，索引为: 3

通过这些可视化示例，你可以更好地理解「线性搜索和二分搜索」算法的执行过程。