[[439902]]

本文介紹以下查找算法：

線性查找(Linear Search)

二分查找(Binary Search)

插值查找(Interpolation Search)

我們詳細(xì)了解一下它們各自的情況。

一. 線性查找

查找數(shù)據(jù)的最簡單策略就是線性查找，它簡單地遍歷每個元素以尋找目標(biāo)，訪問每個數(shù)據(jù)點(diǎn)從而查找匹配項(xiàng)，找到匹配項(xiàng)后，返回結(jié)果，算法退出循環(huán)，否則，算法將繼續(xù)查找，直到到達(dá)數(shù)據(jù)末尾。線性查找的明顯缺點(diǎn)是，由于固有的窮舉搜索，它非常慢。它的優(yōu)點(diǎn)是無須像其他算法那樣，需要數(shù)據(jù)排好序。

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

def LinearSearch(list, item): 
    index = 0 
    found = False 
 
# Match the value with each data element        
    while index < len(list) and found is False: 
        if list[index] == item: 
            found = True 
        else: 
            index = index + 1 
    return found 

現(xiàn)在，看一下代碼的輸出(見圖3-15)。

list = [12, 33, 11, 99, 22, 55, 90] 
 
print(LinearSearch(list, 12)) 
 
print(LinearSearch(list, 91)) 

▲圖 3-15

需要注意的是，如果能成功找到數(shù)據(jù)，運(yùn)行LinearSearch函數(shù)會返回True。

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

二. 二分查找

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

def BinarySearch(list, item): 
    first = 0 
    last = len(list)-1 
    found = False 
 
    while first<=last and not found: 
        midpoint = (first + last)//2 
        if list[midpoint] == item: 
            found = True 
        else: 
            if item < list[midpoint]: 
                last = midpoint-1 
            else: 
                first = midpoint+1 
    return found 

輸出結(jié)果如圖3-16所示。

list = [12, 33, 11, 99, 22, 55, 90] 
 
sorted_list = BubbleSort(list) 
 
print(BinarySearch(list, 12)) 
 
print(BinarySearch(list, 91)) 

▲圖 3-16

請注意，如果在輸入列表中找到了值，調(diào)用BinarySearch函數(shù)將返回True。

• 二分查找的性能：二分查找之所以如此命名，是因?yàn)樵诿看蔚?，算法都會將?shù)據(jù)分成兩部分。如果數(shù)據(jù)有N項(xiàng)，則它最多需要O(log N)步來完成迭代，這意味著算法的運(yùn)行時(shí)間為O(log N)。

三. 插值查找

二分查找的基本邏輯是關(guān)注數(shù)據(jù)的中間部分。插值查找更加復(fù)雜，它使用目標(biāo)值來估計(jì)元素在有序數(shù)組中的大概位置。

讓我們試著用一個例子來理解它：假設(shè)我們想在一本英文詞典中搜索一個單詞，比如單詞river，我們將利用這些信息進(jìn)行插值，并開始查找以字母r開頭的單詞，而不是翻到字典的中間開始查找。一個更通用的插值查找程序如下所示：

def IntPolsearch(list,x ): 
    idx0 = 0 
    idxn = (len(list) - 1) 
    found = False 
    while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]: 
 
# Find the mid point 
        mid = idx0 +int(((float(idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0]))) 
 
# Compare the value at mid point with search value  
        if list[mid] == x: 
            found = True 
            return found 
 
        if list[mid] < x: 
            idx0 = mid + 1 
    return found 

輸出結(jié)果如圖3-17所示。

list = [12, 33, 11, 99, 22, 55, 90] 
 
sorted_list = BubbleSort(list) 
 
print(IntPolsearch(list, 12)) 
 
print(IntPolsearch(list,91)) 

▲圖 3-17

請注意，在使用IntPolsearch函數(shù)之前，首先需要使用排序算法對數(shù)組進(jìn)行排序。

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

關(guān)于作者：伊姆蘭·艾哈邁德(Imran Ahmad) 是一名經(jīng)過認(rèn)證的谷歌講師，多年來一直在谷歌和學(xué)習(xí)樹(Learning Tree)任教，主要教授Python、機(jī)器學(xué)習(xí)、算法、大數(shù)據(jù)和深度學(xué)習(xí)。他在攻讀博士學(xué)位期間基于線性規(guī)劃方法提出了名為ATSRA的新算法，用于云計(jì)算環(huán)境中資源的優(yōu)化分配。近4年來，他一直在加拿大聯(lián)邦政府的高級分析實(shí)驗(yàn)室參與一個備受關(guān)注的機(jī)器學(xué)習(xí)項(xiàng)目。

本文摘編自《程序員必會的40種算法》，經(jīng)出版方授權(quán)發(fā)布。