快捷導(dǎo)航

python數(shù)據(jù)結(jié)構(gòu)之搜索講解

更新時(shí)間：2022年01月25日 10:36:39 作者：柳小蔥

這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之搜索講解,搜索是指從元素集合中找到某個(gè)特定元素的算法過(guò)程。搜索過(guò)程通常返回?True?或?False，?分別表示元素是否存在,下面一起來(lái)了解文章的詳細(xì)內(nèi)容吧，希望對(duì)你有所幫助

python數(shù)據(jù)類(lèi)型: python數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類(lèi)型.
python的輸入輸出: python數(shù)據(jù)結(jié)構(gòu)之輸入輸出及控制和異常.
python面向?qū)ο? python數(shù)據(jù)結(jié)構(gòu)面向?qū)ο?
python算法分析: python數(shù)據(jù)結(jié)構(gòu)之算法分析.
python棧、隊(duì)列和雙端隊(duì)列:python數(shù)據(jù)結(jié)構(gòu)棧、隊(duì)列和雙端隊(duì)列.
python遞歸: python數(shù)據(jù)結(jié)構(gòu)之遞歸.

上一期講的遞歸，對(duì)于初學(xué)者其實(shí)是不太友好的，遞歸需要自己多去接觸，自己多畫(huà)畫(huà)圖，這樣可以加強(qiáng)理解遞歸的過(guò)程，本期我們要講的內(nèi)容是搜索，也可以叫查找。我將講解幾種最為普遍的查找算法。

1. 普通搜索

搜索是指從元素集合中找到某個(gè)特定元素的算法過(guò)程。搜索過(guò)程通常返回 True 或 False，分別表示元素是否存在。
python中提供了 in 方法可以判斷元素是否存在列表中：

# python提供in函數(shù)進(jìn)行搜索
a=[3,4,5,8,'t']
't' in a
9 in a

結(jié)果如下：

2. 順序搜索

順序搜索故名思義：從列表中的第一個(gè)元素開(kāi)始，沿著默認(rèn)的順序逐個(gè)查看，直到找到目標(biāo)元素或者查完列表。如果查完列表后仍沒(méi)有找到目標(biāo)元素，則說(shuō)明目標(biāo)元素不在列表中。

順序搜索過(guò)程：

1.1 無(wú)序下的順序查找

無(wú)序下的順序搜索很有特點(diǎn)，列表無(wú)序，只好一個(gè)一個(gè)去比較，尋找元素。

#順序查找
def sequentialsearch(testlist,item):
    pos=0
    found=False
    while pos<len(testlist) and not found:
        if testlist[pos]==item:
            found=True
        else:
            pos=pos+1
    return found

結(jié)果如下：

分析一下這種順序查找，這種查找方式，最好的方式就尋找一次就成功了，最壞的情況的需要查找n次，于是時(shí)間復(fù)雜度是O(n)

1.2 有序下的順序查找

有序下的順序查找就是所查找的列表是有序的，

# 有序下的順序搜索
def ordersearch(testlist,item):
    pos=0
    found=False
    stop=False
    while pos<len(testlist) and not found and not stop:
        if testlist[pos]==item:
            found=True
        else:
            if testlist[pos]>item:
                stop=True
            else:
                pos=pos+1
    return found

結(jié)果如下：

分析一下這種搜索方法，正常情況下來(lái)說(shuō)，最好情況下，搜索1次就能成功，最差情況只需要n/2次即可搜索完成，但時(shí)間復(fù)雜度依舊是O(n)，只有當(dāng)列表中不存在目標(biāo)元素時(shí)，有序排列的元素才會(huì)提高順序搜索的效率。

2.二分查找

二分查找：是利用列表有序的這個(gè)原理，從中間的元素著手。如果這個(gè)元素就是目標(biāo)元素，那就立即停止搜索；如果不是，則可以利用列表有序的特性，排除一半的元素。如果目標(biāo)元素比中間的元素大，就可以直接排除列表的左半部分和中間的元素。這是因?yàn)椋绻斜戆繕?biāo)元素，它必定位于右半部分。

在有序整數(shù)列表中進(jìn)行二分搜索：

二分查找實(shí)現(xiàn)方式：

def binarysearch(testlist,item):
    testlist.sort()#排序
    left=0#左指針
    right=len(testlist)-1#右指針
    found=False
    while left<=right and not found:
        mid=(left+right)//2#取中間值
        if testlist[mid]==item:
            found=True
        else:
            if testlist[mid]<item:
                left=mid+1
            else:
                right=mid-1
    return found

看看效果：

二分查找遞歸實(shí)現(xiàn)：

def binarysearch2(testlist,item):
     if len(testlist) == 0: 
        return False 
     else: 
        mid = len(testlist) // 2 
        if testlist[mid] == item: 
            return True 
        else: 
            if item < testlist[mid]: 
                return binarysearch2(testlist[:mid], item) 
            else: 
                return binarysearch2(testlist[mid+1:], item)

看看效果：

總結(jié)一下二分查找：在進(jìn)行二分搜索時(shí)，每一次比較都將待考慮的元素減半，。那么，要檢查完整個(gè)列表，二分搜索算法最多要比較多少次呢？假設(shè)列表共有 n 個(gè)元素，第一次比較后剩下n 個(gè)元素，第 2 次比較2后剩下n /4個(gè)元素，接下來(lái)是n/8 ，然后是n/16 ，依此類(lèi)推。列表能拆分多少次？

二分搜索算法的表格分：

3.散列查找

散列查找：通過(guò)散列構(gòu)建一個(gè)時(shí)間復(fù)雜度為 O(1)的數(shù)據(jù)結(jié)構(gòu)。我們平常聽(tīng)的最多哈希表就是散列的一種方式。
散列表：散列表是元素集合，其中的元素以一種便于查找的方式存儲(chǔ)。散列表中的每個(gè)位置通常被稱(chēng) 為槽，其中可以存儲(chǔ)一個(gè)元素。槽用一個(gè)從 0 開(kāi)始的整數(shù)標(biāo)記，例如 0 號(hào)槽、1 號(hào)槽、2 號(hào)槽，等等。初始情形下，散列表中沒(méi)有元素，每個(gè)槽都是空的?？梢杂昧斜韥?lái)實(shí)現(xiàn)散列表，并將每個(gè)元素都初始化為 Python 中的特殊值 None。下圖展示了大小 m 為 11 的散列表。也就是說(shuō)，表中有 m 個(gè)槽，編號(hào)從 0 到 10。

有11 個(gè)槽的散列表：

：

散列函數(shù):將散列表中的元素與其所屬位置對(duì)應(yīng)起來(lái)。對(duì)散列表中的任一元素，散列函數(shù)返回一個(gè)介于 0 和 m – 1 之間的整數(shù)。假設(shè)有一個(gè)由整數(shù)元素 54、26、93、17、77 和 31 構(gòu)成的集合。首先來(lái)看第一個(gè)散列函數(shù)，它有時(shí)被稱(chēng)作“取余函數(shù)”，即用一個(gè)元素除以表的大小，并將得到的余數(shù)作為散列值（h(item) = item%11）。下圖給出了所有示例元素的散列值。取余函數(shù)是一個(gè)很常見(jiàn)的散列函數(shù)，這是因?yàn)榻Y(jié)果必須在槽編號(hào)范圍內(nèi)。

使用余數(shù)作為散列值：

計(jì)算出散列值后，就可以將每個(gè)元素插入到相應(yīng)的位置，如圖 5-5 所示。注意，在 11 個(gè)槽中，有 6 個(gè)被占用了。占用率被稱(chēng)作載荷因子，記作λ \lambdaλ，定義如下：

有 6 個(gè)元素的散列表：

3.1 幾種散列函數(shù)

給定一個(gè)元素集合，能將每個(gè)元素映射到不同的槽，這種散列函數(shù)稱(chēng)作完美散列函數(shù)。如果元素已知，并且集合不變，那么構(gòu)建完美散列函數(shù)是可能的。不幸的是，給定任意一個(gè)元素集合，沒(méi)有系統(tǒng)化方法來(lái)保證散列函數(shù)是完美的。所幸，不完美的散列函數(shù)也能有不錯(cuò)的性能。

折疊法：先將元素切成等長(zhǎng)的部分（最后一部分的長(zhǎng)度可能不同），然后將這些部分相加，得到散列值。假設(shè)元素是電話號(hào)碼 436-555-4601，以 2 位為一組進(jìn)行切分，得到 43、65、55、46 和 01。將這些數(shù)字相加后，得到 210。
平方取中法：先將元素取平方，然后提取中間幾位數(shù)。如果元素是 44，先計(jì)算 442=1936，然后提取中間兩位 93，繼續(xù)進(jìn)行取余的步驟。
字符編碼：采用python中的ord函數(shù)將單詞“cat”看作序數(shù)值序列，再將這些序數(shù)值相加，并采用取余法得到散列值。

3.2 處理散列表沖突

完美的散列表，一個(gè)元素只對(duì)應(yīng)著一個(gè)卡槽，可是如果當(dāng)2個(gè)元素被分配到一個(gè)卡槽時(shí)，必須通過(guò)一種系統(tǒng)化方法在散列表中安置第二個(gè)元素。這個(gè)過(guò)程被稱(chēng)為處理沖突。

開(kāi)發(fā)定址法：在散列表中找到另一個(gè)空槽，用于放置引起沖突的元素。簡(jiǎn)單的做法是從起初的散列值開(kāi)始，順序遍歷散列表，直到找到一個(gè)空槽。注意，為了遍歷散列表，可能需要往回檢查第一個(gè)槽。（例如：將（54, 26, 93, 17, 77, 31, 44, 55, 20）放入卡槽中。）

3.3 散列表的實(shí)現(xiàn)（加1重復(fù)）

哈希散列的實(shí)現(xiàn)：

#哈希表
class HashTable:
    def __init__(self): 
        self.size = 11 
        self.slots = [None] * self.size 
        self.data = [None] * self.size
    def put(self, key, data): 
        hashvalue = self.hashfunction(key, len(self.slots)) 
        if self.slots[hashvalue] == None: 
            self.slots[hashvalue] = key
            self.data[hashvalue] = data 
        else: 
            if self.slots[hashvalue] == key: 
                self.data[hashvalue] = data #替換 
            else: 
                nextslot = self.rehash(hashvalue, len(self.slots)) 
                while self.slots[nextslot] != None and self.slots[nextslot] != key: 
                    nextslot = self.rehash(nextslot, len(self.slots))
                if self.slots[nextslot] == None: 
                    self.slots[nextslot] = key 
                    self.data[nextslot] = data
                else: 
                    self.data[nextslot] = data #替換 
    def hashfunction(self, key, size): 
        return key%size 
    def rehash(self, oldhash, size): 
        return (oldhash + 1)%size

#get函數(shù)
    def get(self, key): 
        startslot = self.hashfunction(key, len(self.slots)) 
        data = None 
        stop = False 
        found = False 
        position = startslot
        while self.slots[position] != None and not found and not stop: 
            if self.slots[position] == key: 
                found = True 
                data = self.data[position] 
            else:  
                position=self.rehash(position, len(self.slots)) 
                if position == startslot: 
                    stop = True 
                    return data 
    def __getitem__(self, key): 
        return self.get(key) 
    def __setitem__(self, key, data): 
        self.put(key, data)

結(jié)果如下：