3.2　查找算法簡介

在復雜的數據結構中高效地查找數據是其非常重要的功能之一。最簡單的方法是在每個數據點中查找所需數據，效率并不高。因此隨著數據規模的增加，我們需要設計更復雜的算法來查找數據。

本節介紹以下查找算法：

• 線性查找（Linear Search）
• 二分查找（Binary Search）
• 插值查找（Interpolation Search）

我們詳細了解一下它們各自的情況。

3.2.1　線性查找

查找數據的最簡單策略就是線性查找，它簡單地遍歷每個元素以尋找目標，訪問每個數據點從而查找匹配項，找到匹配項后，返回結果，算法退出循環，否則，算法將繼續查找，直到到達數據末尾。線性查找的明顯缺點是，由于固有的窮舉搜索，它非常慢。它的優點是無須像本章介紹的其他算法那樣，需要數據排好序。

我們看一下線性查找的代碼：

現在，看一下代碼的輸出（見圖3-15）。

需要注意的是，如果能成功找到數據，運行LinearSearch函數會返回True。

線性查找的性能

如上所述，線性查找是一種執行窮舉搜索的簡單算法，其最壞時間復雜度是O(N)。

3.2.2　二分查找

二分查找算法的前提條件是數據有序。算法反復地將當前列表分成兩部分，跟蹤最低和最高的兩個索引，直到找到它要找的值為止：

輸出結果如圖3-16所示。

請注意，如果在輸入列表中找到了值，調用BinarySearch函數將返回True。

二分查找的性能

二分查找之所以如此命名，是因為在每次迭代中，算法都會將數據分成兩部分。如果數據有N項，則它最多需要O(log N)步來完成迭代，這意味著算法的運行時間為O(log N)。

3.2.3　插值查找

二分查找的基本邏輯是關注數據的中間部分。插值查找更加復雜，它使用目標值來估計元素在有序數組中的大概位置。讓我們試著用一個例子來理解它：假設我們想在一本英文詞典中搜索一個單詞，比如單詞river，我們將利用這些信息進行插值，并開始查找以字母r開頭的單詞，而不是翻到字典的中間開始查找。一個更通用的插值查找程序如下所示：

輸出結果如圖3-17所示。

請注意，在使用IntPolsearch函數之前，首先需要使用排序算法對數組進行排序。

插值查找的性能

如果數據分布不均勻，則插值查找算法的性能會很差，該算法的最壞時間復雜度是O(N)。如果數據分布得相當均勻，則最佳時間復雜度是O(log(log N))。