线性搜索

执行搜索的最常见方法之一是将每个项目与我们正在寻找的项目进行比较。这被称为线性搜索或顺序搜索。这是执行搜索的最基本方法。如果我们认为一个列表中有 n 个条目，那么在最坏的情况下，我们必须搜索 n 个条目才能找到一个特定的条目。我们可以遍历一个列表或数组来查找一个项目。让我们来看看下面的例子：

我们有一个名为 search 的函数，它需要两个参数。一个是数字列表，另一个是我们要在列表中查找的数字。我们正在运行一个 for 循环，遍历列表中的每个项目，并将它们与我们的项目进行比较。如果找到匹配项，我们就返回 true，不再继续搜索。但是，如果循环结束后仍未找到匹配项，我们就会在函数定义的末尾返回 false。让我们用下面的程序使用搜索函数来找东西：

在这里，我们使用 PHP 的内置函数 range 生成一个随机数组，范围为 1 到 200（包括 200）。每个项目都有一个 5 的间隔，如 1、6、11、16 等；然后我们搜索 31，它在列表中，因为我们有 6、11、16、21、26、31 等。但是，如果我们要搜索 32 或 33，那么将找不到该项目。因此，在这种情况下，我们的输出结果将是 Found。

在这里，我们需要记住的一点是，我们并不担心我们的列表是否按特定顺序排列或以某种方式组织。如果我们要找的项目排在第一位，这将是最好的结果。最差的结果可能是最后一个项目或不在列表中的项目。在这两种情况下，我们都必须遍历列表中的所有 n 个项目。下面是线性/顺序搜索的复杂度：

我们可以看到，线性搜索的平均或最差时间复杂度为 \$O(n)\$，而这并不改变我们如何对项目列表进行排序。现在，如果数组中的项目是按特定顺序排列的，那么我们可能就不必进行线性搜索，而可以通过选择性搜索或计算性搜索获得更好的结果。最流行、最著名的搜索算法是 "二进制搜索"。没错，它听起来就像 第 6 章 "理解和实现树" 中学习的二叉搜索树，但我们甚至不需要构建二叉搜索树就能使用这种算法。那么，让我们来探讨一下。