快捷導(dǎo)航

Python中的查找算法代碼實(shí)例

更新時(shí)間：2023年07月27日 10:40:34 作者：小白地瓜

這篇文章主要介紹了Python中的查找算法代碼實(shí)例,算法是解決一系列問(wèn)題的清晰指令，也就是，能對(duì)一定規(guī)范的輸入，在有限的時(shí)間內(nèi)獲得所要求的輸出,簡(jiǎn)單來(lái)說(shuō)，算法就是解決一個(gè)問(wèn)題的具體方法和步驟,算法是程序的靈魂,需要的朋友可以參考下

一. 順序查找

條件：無(wú)序或有序隊(duì)列。

原理：按順序比較每個(gè)元素，直到找到關(guān)鍵字為止。

時(shí)間復(fù)雜度：O(n)

def sequential_search(lis, key):
    length = len(lis)
    for i in range(length):
        print(lis[i], key)
        if lis[i] == key:
            return i
    return False
if __name__ == '__main__':
    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
    result = sequential_search(LIST, 123)
    print(result)

二. 二分查找

條件：有序數(shù)組

原理：查找過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜素過(guò)程結(jié)束；

如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。

如果在某一步驟數(shù)組為空，則代表找不到。

這種搜索算法每一次比較都使搜索范圍縮小一半。

時(shí)間復(fù)雜度：O(logn)

lst = [11, 22, 33, 44, 55, 66, 77, 88, 99, 123, 234, 345, 456, 567, 678, 789]
def func(alist, data):
    first = 0
    last = len(alist) - 1
    while first <= last:
        mid = (last + first) // 2
        if alist[mid] > data:
            last = mid - 1
        elif alist[mid] < data:
            first = mid + 1
        else:
            return mid
    return -1
print(func(lst, 678))

三. 插值查找

應(yīng)用: 根據(jù)關(guān)鍵字的分布估計(jì)被查元素的位置，能更精確定位到被查找元素的位置，但應(yīng)用有限

公式：mid = low + (key - low) / (a[high] - a[low]) * (high - low)

對(duì)于數(shù)據(jù)量較大，關(guān)鍵字分布比較均勻的查找表來(lái)說(shuō)，采用插值查找, 速度較快

關(guān)鍵字分布不均勻的情況下，該方法不一定比折半查找要好

def binary_search(lis, key):
    low = 0
    high = len(lis) - 1
    while low < high:
        mid = low + int((high - low) * (key - lis[low]) / (lis[high] - lis[low]))
        if key < lis[mid]:
            high = mid - 1
        elif key > lis[mid]:
            low = mid + 1
        else:
            return mid
    return False
LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
result = binary_search(LIST, 99)
print(result)

到此這篇關(guān)于Python中的查找算法代碼實(shí)例的文章就介紹到這了,更多相關(guān)Python查找算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: