Python 算法基础篇之线性搜索算法：顺序搜索、二分搜索

小蓝枣

发布于 2023-07-24 15:10:41

3020

发布于 2023-07-24 15:10:41

Python 算法基础篇之线性搜索算法：顺序搜索、二分搜索

引用

在算法和数据结构中，搜索是一种常见的操作，用于查找特定元素在数据集合中的位置。线性搜索算法是最简单的搜索算法之一，在一组数据中逐一比较查找目标元素。本篇博客将介绍线性搜索算法的两种实现方式：顺序搜索和二分搜索，并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 顺序搜索算法

顺序搜索算法，也称为线性搜索算法，是一种基本的搜索方法。它从数据集合的第一个元素开始逐一与目标元素进行比较，直到找到目标元素或搜索完整个数据集合。下面是一个顺序搜索的示例代码：

def linear_search(arr, target):
    """
    顺序搜索算法
    :param arr: 待搜索的列表
    :param target: 目标元素
    :return: 目标元素的索引，如果不存在返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 测试顺序搜索算法
arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
target = 6
result = linear_search(arr, target)
if result != -1:
    print(f"目标元素 {target} 在列表中的索引为：{result}")
else:
    print(f"目标元素 {target} 不存在于列表中")

代码解释：上述代码定义了一个 linear_search 函数来实现顺序搜索算法。函数接受一个待搜索的列表 arr 和目标元素 target 作为参数。在循环中，依次遍历列表中的元素，若找到目标元素，则返回其索引；若搜索完整个列表仍未找到目标元素，则返回- 1 表示目标元素不存在于列表中。

顺序搜索算法的时间复杂度为 O ( n )，其中 n 是列表的长度。这意味着顺序搜索的时间随着数据集合的增大而线性增加。

2. 二分搜索算法

二分搜索算法，也称为折半搜索算法，是一种高效的搜索方法，前提是数据集合必须是有序的。它将数据集合一分为二，然后判断目标元素可能在哪一半，并继续在该半部分执行二分搜索，直到找到目标元素或搜索范围缩小为零。下面是一个二分搜索的示例代码：

def binary_search(arr, target):
    """
    二分搜索算法
    :param arr: 已排序的列表
    :param target: 目标元素
    :return: 目标元素的索引，如果不存在返回-1
    """
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 测试二分搜索算法
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 6
result = binary_search(arr, target)
if result != -1:
    print(f"目标元素 {target} 在列表中的索引为：{result}")
else:
    print(f"目标元素 {target} 不存在于列表中")

代码解释：上述代码定义了一个 binary_search 函数来实现二分搜索算法。函数接受一个已排序的列表 arr 和目标元素 target 作为参数。在循环中，通过不断缩小搜索范围，将数据集合一分为二，然后判断目标元素可能在哪一半部分，继续在该半部分执行二分搜索。若找到目标元素，则返回其索引；若搜索范围缩小为零仍未找到目标元素，则返回- 1 表示目标元素不存在于列表中。

二分搜索算法的时间复杂度为 O ( log n )，其中 n 是列表的长度。这意味着二分搜索的时间随着数据集合的增大而以对数速

率增加。

3. 顺序搜索和二分搜索的对比

顺序搜索和二分搜索是两种不同的搜索算法，在不同的场景下有不同的适用性。

a ) 适用性

顺序搜索适用于无序列表和简单的数据结构，它不依赖于数据集合是否有序。当数据集合规模较小，或者不确定是否有序时，顺序搜索是一个简单且可行的选择。

二分搜索适用于已排序的列表和复杂的数据结构，它利用了数据集合的有序性，通过不断缩小搜索范围来高效地查找目标元素。在数据集合规模较大且已排序的情况下，二分搜索是一个高效的搜索算法。

b ) 时间复杂度

顺序搜索的时间复杂度为 O ( n )，其中 n 是列表的长度。最坏情况下，需要遍历整个列表才能找到目标元素。

二分搜索的时间复杂度为 O ( log n )，其中 n 是列表的长度。二分搜索通过不断将搜索范围缩小为原来的一半，因此时间复杂度较低。

c ) 前提条件

顺序搜索不需要数据集合是有序的，可以直接应用于无序列表。

二分搜索必须在已排序的列表上执行，否则无法保证正确的结果。

4. 实例演示

现在，让我们通过两个实例来演示顺序搜索和二分搜索的应用。

实例1：顺序搜索

假设我们有一个存储学生姓名的列表，现在我们需要查找是否有特定的学生姓名在列表中。下面是一个实例代码：

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

students = ['Alice', 'Bob', 'Charlie', 'David', 'Emma', 'Frank']
target_name = 'David'
result = linear_search(students, target_name)
if result != -1:
    print(f"{target_name} 存在于列表中，索引为：{result}")
else:
    print(f"{target_name} 不存在于列表中")

代码解释：上述代码演示了顺序搜索算法在学生姓名列表中查找特定姓名的应用。假设我们需要查找学生姓名为’ David ‘的学生是否在列表中。通过顺序搜索，我们遍历整个列表，并找到了目标姓名’ David '在列表中的索引位置。

实例2：二分搜索

现在，我们假设我们有一个存储整数的有序列表，我们需要查找是否有特定的整数在列表中。下面是一个实例代码：

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

sorted_nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search(sorted_nums, target)
if result != -1:
    print(f"{target} 存在于列表中，索引为：{result}")
else:
    print(f"{target} 不存在于列表中")

代码解释：上述代码演示了二分搜索算法在有序整数列表中查找特定整数的应用。假设我们需要查找整数’ 11 ‘是否在有序列表中。通过二分搜索，我们迅速找到了目标整数’ 11 '在列表中的索引位置。