手把手教你用Python實(shí)現(xiàn)查找算法
導(dǎo)讀：在復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中高效地查找數(shù)據(jù)是其非常重要的功能之一。最簡(jiǎn)單的方法是在每個(gè)數(shù)據(jù)點(diǎn)中查找所需數(shù)據(jù)，效率并不高。因此隨著數(shù)據(jù)規(guī)模的增加，我們需要設(shè)計(jì)更復(fù)雜的算法來查找數(shù)據(jù)。
線性查找（Linear Search） 二分查找（Binary Search） 插值查找（Interpolation Search）
def?LinearSearch(list,?item):
????index?=?0
????found?=?False
#?Match?the?value?with?each?data?element???????
????while?index?and?found?is?False:
????????if?list[index]?==?item:
????????????found?=?True
????????else:
????????????index?=?index?+?1
????return?found
list?=?[12,?33,?11,?99,?22,?55,?90]
print(LinearSearch(list,?12))
print(LinearSearch(list,?91))
線性查找的性能：如上所述，線性查找是一種執(zhí)行窮舉搜索的簡(jiǎn)單算法，其最壞時(shí)間復(fù)雜度是O(N)。
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?????????????????last?=?midpoint-1
????????????else:
????????????????first?=?midpoint+1
????return?found
list?=?[12,?33,?11,?99,?22,?55,?90]
sorted_list?=?BubbleSort(list)
print(BinarySearch(list,?12))
print(BinarySearch(list,?91))
二分查找的性能：二分查找之所以如此命名，是因?yàn)樵诿看蔚校惴ǘ紩?huì)將數(shù)據(jù)分成兩部分。如果數(shù)據(jù)有N項(xiàng)，則它最多需要O(log N)步來完成迭代，這意味著算法的運(yùn)行時(shí)間為O(log N)。
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]?????????????idx0?=?mid?+?1
????return?found
list?=?[12,?33,?11,?99,?22,?55,?90]
sorted_list?=?BubbleSort(list)
print(IntPolsearch(list,?12))
print(IntPolsearch(list,91))
插值查找的性能：如果數(shù)據(jù)分布不均勻，則插值查找算法的性能會(huì)很差，該算法的最壞時(shí)間復(fù)雜度是O(N)。如果數(shù)據(jù)分布得相當(dāng)均勻，則最佳時(shí)間復(fù)雜度是O(log(log N))。
干貨直達(dá)??
評(píng)論
圖片
表情