手把手教你用 Python 實現(xiàn)查找算法
本文介紹以下查找算法：
線性查找(Linear Search)
二分查找(Binary Search)
插值查找(Interpolation Search)
我們詳細了解一下它們各自的情況。
一. 線性查找
查找數(shù)據(jù)的最簡單策略就是線性查找，它簡單地遍歷每個元素以尋找目標，訪問每個數(shù)據(jù)點從而查找匹配項，找到匹配項后，返回結(jié)果，算法退出循環(huán)，否則，算法將繼續(xù)查找，直到到達數(shù)據(jù)末尾。線性查找的明顯缺點是，由于固有的窮舉搜索，它非常慢。它的優(yōu)點是無須像其他算法那樣，需要數(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ù)，運行LinearSearch函數(shù)會返回True。
- 線性查找的性能：如上所述，線性查找是一種執(zhí)行窮舉搜索的簡單算法，其最壞時間復雜度是O(N)。
二. 二分查找
二分查找算法的前提條件是數(shù)據(jù)有序。算法反復地將當前列表分成兩部分，跟蹤最低和最高的兩個索引，直到找到它要找的值為止：
- 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。
- 二分查找的性能：二分查找之所以如此命名，是因為在每次迭代中，算法都會將數(shù)據(jù)分成兩部分。如果數(shù)據(jù)有N項，則它最多需要O(log N)步來完成迭代，這意味著算法的運行時間為O(log N)。
三. 插值查找
二分查找的基本邏輯是關(guān)注數(shù)據(jù)的中間部分。插值查找更加復雜，它使用目標值來估計元素在有序數(shù)組中的大概位置。
讓我們試著用一個例子來理解它：假設(shè)我們想在一本英文詞典中搜索一個單詞，比如單詞river，我們將利用這些信息進行插值，并開始查找以字母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ù)組進行排序。
- 插值查找的性能：如果數(shù)據(jù)分布不均勻，則插值查找算法的性能會很差，該算法的最壞時間復雜度是O(N)。如果數(shù)據(jù)分布得相當均勻，則最佳時間復雜度是O(log(log N))。
關(guān)于作者：伊姆蘭·艾哈邁德(Imran Ahmad) 是一名經(jīng)過認證的谷歌講師，多年來一直在谷歌和學習樹(Learning Tree)任教，主要教授Python、機器學習、算法、大數(shù)據(jù)和深度學習。他在攻讀博士學位期間基于線性規(guī)劃方法提出了名為ATSRA的新算法，用于云計算環(huán)境中資源的優(yōu)化分配。近4年來，他一直在加拿大聯(lián)邦政府的高級分析實驗室參與一個備受關(guān)注的機器學習項目。
本文摘編自《程序員必會的40種算法》，經(jīng)出版方授權(quán)發(fā)布。
