Data Structures Algorithms 简明教程
Linear Search Algorithm
线性搜索是一种顺序搜索算法。在此方法中，遍历输入数组中的每个元素，并将其与要查找的关键元素进行比较。如果在数组中找到匹配项，则搜索成功；如果没有找到匹配项，则搜索失败，并给出最坏情况的时间复杂度。
例如，在给定的动画图表中，我们正在搜索元素 33。因此，线性搜索方法从第一个元素开始顺序搜索它，直到找到匹配项。这会返回一个成功的搜索。
在同一图表中，如果我们必须搜索元素 46，则它会返回一个不成功的搜索，因为输入中没有 46。
Linear Search Algorithm
线性搜索的算法相对简单。过程从要搜索的输入数组的第一个索引开始。
Step 1 − 从输入数组的第 0 个索引开始，将键值与第 0 个索引中存在的那个值进行比较。
Step 2 − 如果值与键匹配，则返回找到值的位置。
Step 3 − 如果值与键不匹配，则比较数组中的下一个元素。
Step 4 − 重复步骤 3，直到找到匹配。返回找到匹配的位置。
Step 5 − 如果搜索不成功，则打印元素不存在于数组中并退出程序。
Pseudocode
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedureAnalysis
线性搜索顺序遍历每个元素，因此，当在第一次迭代中找到该元素时为最佳情况。最佳情况时间的复杂度是 O(1) 。
但是，线性搜索方法的最坏情况是未成功的搜索，即未在数组中找到键值，它执行 n 次迭代。因此，线性搜索算法的最坏情况时间复杂度是 O(n) 。
Example
让我们看看使用线性搜索方法在数组中逐步搜索键元素（假设为 47）。
Step 1
线性搜索从第 0 个索引开始。将键元素与第 0 个索引中的值 34 进行比较。
但是，47 ≠ 34。因此，它移至下一个元素。
Step 2
现在，将该键与数组的第一个索引中的值进行比较。
仍然是 47 ≠ 10，使得算法移至另一个迭代。
Step 3
将下一个元素 66 与 47 进行比较。两者都不匹配，因此算法比较了后面的元素。
Step 4
现在，第 3 个索引中的元素 27 与键值 47 进行比较。它们不相等，因此算法推进到检查下一个元素。
Step 5
比较数组中第 4 个索引处的元素 47 与键 47。可以看出两个元素匹配。现在，返回 47 存在的位置，即 4。
获得的输出是“在第 4 个索引处找到元素”。