1.5　查找

如前所述，查找意味著判斷數組中是否存在特定值。如果存在，那么查找操作還要給出它的索引。

在某種意義上，查找與讀取正好相反。讀取是給計算機提供一個索引，并讓它返回位于該索引的值。查找則是給計算機提供一個值，并讓它返回那個值的索引。

雖然這兩個操作聽起來類似，但效率有著天壤之別。因為計算機能跳轉到任意索引并找到它的值，所以從一個索引讀取值很快。但查找就麻煩多了，因為計算機不能跳轉到特定值。

這是計算機的一個重要特性：可以立刻訪問所有內存地址，但它事先不知道每個內存地址存儲的值。

還是以之前的水果和蔬菜數組為例。計算機無法立刻弄清每個格子的內容。對計算機來說，這個數組看起來就像下圖這樣。

要查找數組中的水果，計算機只能一次檢查一個格子，別無他法。

接下來的幾幅圖展示了計算機在數組內查找"dates"的過程。

首先，計算機會檢查索引0，如下圖所示。

因為索引0的值是"apples"，而不是要找的"dates"，所以計算機會移動到下一個索引，如下圖所示。

因為索引1也不是"dates"，所以計算機會移動到索引2，如下圖所示。

我們還是不太幸運，所以計算機繼續移動到下一個格子，如下圖所示。

啊哈！終于在索引3處找到了這個“躲躲閃閃”的"dates"。現在計算機不用再移動到下一個格子了，因為它已經找到了要查找的值。

在這個例子中，因為計算機必須檢查4個格子才能找到所要查找的值，所以可以說這一次操作一共用了4步。

在第2章中，你會學習另一種查找數組的方法。上述這種一次檢查一個格子的基本查找操作稱為線性查找。

線性查找一個數組最多需要多少步呢？

如果要找的值剛好在數組的最后一個格子里（比如"elderberries"），那么計算機就必須檢查數組的每一個格子。如果數組中根本沒有要找的值，那么計算機同樣需要檢查每一個格子，才能確定這個值不在數組中。

所以，對于有5個格子的數組，線性查找最多需要5步。對于有500個格子的數組，線性查找最多需要500步。

換言之，對于有N個格子的數組，線性查找最多需要N步。在此語境下，N是一個變量，可以是任意數。

無論如何，查找都不如讀取效率高。這是因為查找可能需要很多步，而讀取任意大小的數組都只需要1步。

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