![秒懂算法:用常识解读数据结构与算法](https://wfqqreader-1252317822.image.myqcloud.com/cover/758/45372758/b_45372758.jpg)
1.5 查找
如前所述,查找意味着判断数组中是否存在特定值。如果存在,那么查找操作还要给出它的索引。
在某种意义上,查找与读取正好相反。读取是给计算机提供一个索引,并让它返回位于该索引的值。查找则是给计算机提供一个值,并让它返回那个值的索引。
虽然这两个操作听起来类似,但效率有着天壤之别。因为计算机能跳转到任意索引并找到它的值,所以从一个索引读取值很快。但查找就麻烦多了,因为计算机不能跳转到特定值。
这是计算机的一个重要特性:可以立刻访问所有内存地址,但它事先不知道每个内存地址存储的值。
还是以之前的水果和蔬菜数组为例。计算机无法立刻弄清每个格子的内容。对计算机来说,这个数组看起来就像下图这样。
![](https://epubservercos.yuewen.com/BDEDD8/24438780101643106/epubprivate/OEBPS/Images/8.jpg?sign=1739274662-7M9btvJaiX54UfzjVE5nLarDwrmwMd9e-0-dde51ae13ffb3116f1440db3324c8c3e)
要查找数组中的水果,计算机只能一次检查一个格子,别无他法。
接下来的几幅图展示了计算机在数组内查找"dates"
的过程。
首先,计算机会检查索引0,如下图所示。
![](https://epubservercos.yuewen.com/BDEDD8/24438780101643106/epubprivate/OEBPS/Images/9.jpg?sign=1739274662-gmUUQRdEjzwwXcV5DdOAFsnMZdaAyk8R-0-649bcf45b58d341c85e6a2e1dc0999fb)
因为索引0的值是"apples"
,而不是要找的"dates"
,所以计算机会移动到下一个索引,如下图所示。
![](https://epubservercos.yuewen.com/BDEDD8/24438780101643106/epubprivate/OEBPS/Images/10.jpg?sign=1739274662-ecuQRfDp91AknnJZWxc6rkBAx7Am2rIU-0-6c2d76f90058d9324f4ee127eb0325aa)
因为索引1也不是"dates"
,所以计算机会移动到索引2,如下图所示。
![](https://epubservercos.yuewen.com/BDEDD8/24438780101643106/epubprivate/OEBPS/Images/11.jpg?sign=1739274662-jWu5YaiBQQrW3TD6xviE3F24gzjWoKy1-0-1117b78887d30b85069857943fe4897e)
我们还是不太幸运,所以计算机继续移动到下一个格子,如下图所示。
![](https://epubservercos.yuewen.com/BDEDD8/24438780101643106/epubprivate/OEBPS/Images/12.jpg?sign=1739274662-Az4fuq8gx6fhQz79ZvrMIftpeMuUivP6-0-d8164f97d05c2a6ad3007cbb92647e16)
啊哈!终于在索引3处找到了这个“躲躲闪闪”的"dates"
。现在计算机不用再移动到下一个格子了,因为它已经找到了要查找的值。
在这个例子中,因为计算机必须检查4个格子才能找到所要查找的值,所以可以说这一次操作一共用了4步。
在第2章中,你会学习另一种查找数组的方法。上述这种一次检查一个格子的基本查找操作称为线性查找。
线性查找一个数组最多需要多少步呢?
如果要找的值刚好在数组的最后一个格子里(比如"elderberries"
),那么计算机就必须检查数组的每一个格子。如果数组中根本没有要找的值,那么计算机同样需要检查每一个格子,才能确定这个值不在数组中。
所以,对于有5个格子的数组,线性查找最多需要5步。对于有500个格子的数组,线性查找最多需要500步。
换言之,对于有N个格子的数组,线性查找最多需要N步。在此语境下,N是一个变量,可以是任意数。
无论如何,查找都不如读取效率高。这是因为查找可能需要很多步,而读取任意大小的数组都只需要1步。
接下来分析插入操作的效率。