1.5　查找

如前所述，查找意味着判断数组中是否存在特定值。如果存在，那么查找操作还要给出它的索引。

在某种意义上，查找与读取正好相反。读取是给计算机提供一个索引，并让它返回位于该索引的值。查找则是给计算机提供一个值，并让它返回那个值的索引。

虽然这两个操作听起来类似，但效率有着天壤之别。因为计算机能跳转到任意索引并找到它的值，所以从一个索引读取值很快。但查找就麻烦多了，因为计算机不能跳转到特定值。

这是计算机的一个重要特性：可以立刻访问所有内存地址，但它事先不知道每个内存地址存储的值。

还是以之前的水果和蔬菜数组为例。计算机无法立刻弄清每个格子的内容。对计算机来说，这个数组看起来就像下图这样。

要查找数组中的水果，计算机只能一次检查一个格子，别无他法。

接下来的几幅图展示了计算机在数组内查找"dates"的过程。

首先，计算机会检查索引0，如下图所示。

因为索引0的值是"apples"，而不是要找的"dates"，所以计算机会移动到下一个索引，如下图所示。

因为索引1也不是"dates"，所以计算机会移动到索引2，如下图所示。

我们还是不太幸运，所以计算机继续移动到下一个格子，如下图所示。

啊哈！终于在索引3处找到了这个“躲躲闪闪”的"dates"。现在计算机不用再移动到下一个格子了，因为它已经找到了要查找的值。

在这个例子中，因为计算机必须检查4个格子才能找到所要查找的值，所以可以说这一次操作一共用了4步。

在第2章中，你会学习另一种查找数组的方法。上述这种一次检查一个格子的基本查找操作称为线性查找。

线性查找一个数组最多需要多少步呢？

如果要找的值刚好在数组的最后一个格子里（比如"elderberries"），那么计算机就必须检查数组的每一个格子。如果数组中根本没有要找的值，那么计算机同样需要检查每一个格子，才能确定这个值不在数组中。

所以，对于有5个格子的数组，线性查找最多需要5步。对于有500个格子的数组，线性查找最多需要500步。

换言之，对于有N个格子的数组，线性查找最多需要N步。在此语境下，N是一个变量，可以是任意数。

无论如何，查找都不如读取效率高。这是因为查找可能需要很多步，而读取任意大小的数组都只需要1步。

接下来分析插入操作的效率。