Python 实现的线性查找
线性查找
线性查找（或顺序查找）是最简单的查找算法。它逐个检查每个元素。
{{ msgDone }}
{{ index }}
运行上面的模拟，查看线性查找算法的工作原理。
该算法非常简单，易于理解和实现。
工作原理：
- 从开头开始，逐个遍历数组中的值。
- 将每个值与我们要查找的值进行比较，看是否相等。
- 如果找到该值，则返回该值的索引。
- 如果遍历到数组末尾仍未找到该值，则返回 -1，表示未找到该值。
如果数组已经排序，最好使用速度更快的二分查找算法，我们将在下一页探讨该算法。
在 Python 中实现线性查找
在 Python 中，检查列表中是否存在某个值的最快方法是使用 in 运算符。
实例
检查列表中是否存在某个值：
mylist = [3, 7, 2, 9, 5, 1, 8, 4, 6]
if 4 in mylist:
print("Found!")
else:
print("Not found!")
但如果需要查找某个值的索引，则需要实现线性查找：
实例
查找列表中某个值的索引：
def linearSearch(arr, targetVal):
for i in range(len(arr)):
if arr[i] == targetVal:
return i
return -1
mylist = [3, 7, 2, 9, 5, 1, 8, 4, 6]
x = 4
result = linearSearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
要实现线性查找算法，我们需要：
- 包含待查找值的数组。
- 要查找的目标值。
- 从开头到结尾遍历数组的循环。
- if 语句，用于将当前值与目标值进行比较，如果找到目标值，则返回当前索引。
- 循环结束后，返回 -1，因为此时我们知道未找到目标值。
线性查找时间复杂度
如果线性查找运行并在包含 \(n\) 个值的数组中，将目标值作为第一个数组值找到，则只需进行一次比较。
但如果线性查找遍历了包含 \(n\) 个值的整个数组，仍未找到目标值，则需要进行 \(n\) 次比较。
这意味着线性查找的时间复杂度为：\( O(n) \)
如果我们绘制线性查找在包含 \(n\) 个值的数组中查找某个值所需的时间图，将得到下图：
