DSA 线性查找

线性查找

线性查找算法遍历数组并返回要查找的值的索引。

运行上面的模拟以查看线性查找算法的工作原理。

要查看当找不到值时会发生什么，请尝试查找值 5。

该算法非常简单易懂且易于实现。

如果数组已经排序，最好使用我们将在下一页介绍的更快得多的二分查找算法。

排序算法和搜索算法之间的主要区别在于，排序算法会修改数组，而搜索算法不会修改数组。

手动运行

让我们尝试手动执行搜索，以便在实际在编程语言中实现它之前，更好地理解线性搜索的工作原理。我们将搜索值 11。

步骤 1：我们从一个包含随机值的数组开始。

步骤 2：我们查看数组中的第一个值，它是否等于 11？

步骤 3：我们移动到索引 1 处的下一个值，并将其与 11 进行比较，以查看它是否相等。

步骤 4：我们检查索引 2 处的下一个值。

步骤 5：我们移动到索引 3 处的下一个值。它是否等于 11？

我们找到了它！

在索引 3 处找到值 11。

返回索引位置 3。

线性查找完成。

运行下面的模拟以查看上述步骤的动画演示

手动运行：发生了什么？

该算法非常直观。

从数组开头开始检查每个值，以查看该值是否等于 11，即我们要查找的值。

当找到该值时，搜索停止，并返回找到该值所在的索引。

如果遍历整个数组而没有找到该值，则返回 -1。

线性查找实现

要实现线性查找算法，我们需要

1. 一个包含要搜索的值的数组。
2. 要搜索的目标值。
3. 一个从头到尾遍历数组的循环。
4. 一个 if 语句，用于将当前值与目标值进行比较，如果找到目标值，则返回当前索引。
5. 在循环之后，返回 -1，因为此时我们知道没有找到目标值。

线性查找的最终代码如下所示

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

arr = [3, 7, 2, 9, 5]
targetVal = 9

result = linearSearch(arr, targetVal)

if result != -1:
    print("Value",targetVal,"found at index",result)
else:
    print("Value",targetVal,"not found")

线性查找时间复杂度

有关时间复杂度的常规解释，请访问此页面。

有关插入排序时间复杂度的更详细解释，请访问此页面。

如果线性查找运行并在一个包含 \(n\) 个值的数组中找到目标值作为第一个数组值，则只需要进行一次比较。

但是，如果线性查找遍历整个包含 \(n\) 个值的数组，而没有找到目标值，则需要进行 \(n\) 次比较。

这意味着线性查找的时间复杂度为

\[ O(n) \]

如果我们绘制线性查找在包含 \(n\) 个值的数组中查找一个值所需的时间，我们会得到以下图形

运行下面的模拟，在包含不同数量值的数组中，并查看线性查找在包含 \(n\) 个值的数组中查找一个值所需进行的比较次数

在上面的模拟中选择“随机”、“降序”或“升序”不会影响线性查找的速度。

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