查找一般要掌握順序查找、二分查找、哈希表查找和二叉排序樹查找。要能夠快速準(zhǔn)確地寫出二分查找的代碼。
1. 順序查找
順序查找就是按照順序表，一個(gè)一個(gè)問哎是不是你是不是你，不是就繼續(xù)問下一個(gè)直到找到為止，簡(jiǎn)單有效的方法。
代碼
tips：代碼實(shí)現(xiàn)中有一個(gè)性能優(yōu)化的點(diǎn)：設(shè)置一個(gè)哨兵(設(shè)置為數(shù)組首元素a(0)或者末元素a(n-1)，將哨兵的值設(shè)置為待查找關(guān)鍵字key的值)，一般首元素a(0)用得比較多，然后查找時(shí)從末元素向前找，若找到就返回相應(yīng)下標(biāo)；若找不到，則返回首元素的下標(biāo)0，表示查找失敗。
# sequentialSearch.py
def sequentialSearch(inputArray, lengthOfArray, searchedKey):
inputArray[0] = searchedKey # 將查找表(即inputArray)的首元素設(shè)置為“哨兵”，并將待查找關(guān)鍵字key的值賦值給“哨兵”
index = lengthOfArray - 1 # 從查找表的末元素開始向前查找
while (inputArray[index] != searchedKey):
index -= 1
return index # 若查找到符合的位置，則返回相應(yīng)位置的下標(biāo)；若返回0，表示查找失敗
if __name__ == "__main__":
inputArray = [0, 3, 9, 6, 45, 32, 68]
lengthOfArray = len(inputArray)
print("lengthOfArray is :", lengthOfArray)
searchedIndex = sequentialSearch(inputArray, lengthOfArray, 45)
print("index of key = 45 is :", searchedIndex)
這里下標(biāo)從1開始，主要是存儲(chǔ)數(shù)據(jù)從1開始，下標(biāo)為0的位置作它用（這里作為哨兵），依據(jù)數(shù)據(jù)結(jié)構(gòu)而定。
最好時(shí)間復(fù)雜度為O(1) --在第一個(gè)位置就找到；
最壞時(shí)間復(fù)雜度為O(n) --在最后一個(gè)位置才找到；
平均時(shí)間復(fù)雜度為O(n)。
2. 有序表查找
一個(gè)線性表有序時(shí)，對(duì)于查找總是很有幫助的。
2.1 二分查找
寫在前面：若要求在排序的數(shù)組（或者部分排序的數(shù)組）中查找一個(gè)數(shù)字或者統(tǒng)計(jì)某個(gè)數(shù)字出現(xiàn)的次數(shù)，可嘗試用二分查找算法。
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。
注意：折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。順序存儲(chǔ)的原因是：查找過程會(huì)對(duì)下標(biāo)進(jìn)行操作，而鏈?zhǔn)酱鎯?chǔ)只能通過p->next的形式尋找后面的元素，無(wú)法對(duì)下標(biāo)進(jìn)行操作。
查找過程
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。
算法時(shí)間復(fù)雜度
O(log2^n) #是以2為底，n的對(duì)數(shù)
對(duì)于二分查找的時(shí)間復(fù)雜度，可以將其映射為二叉樹。最多查找次數(shù)不超過二叉樹的深度即log(2 ^ n)+1（對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為log(2^n)+1）。
代碼
# binarySearch0823 非遞歸實(shí)現(xiàn)
def binarySearch(inputArray, lenOfArray, key):
# low high mid
low = 1
high = lenOfArray
while low <= high :
mid = low + (high - low) // 2
if inputArray[mid] > key:
high = mid - 1
elif inputArray[mid] < key:
low = mid + 1
else:
return mid
return 0
if __name__ == "__main__":
inputArray = [0, 1, 2, 3, 5, 12, 12, 12, 15, 29, 55] #其中，下標(biāo)為0的位置不參與查找
lenOfArray = len(inputArray) - 1
indexOfKey = binarySearch(inputArray, lenOfArray, 15)
if indexOfKey == 0:
print("fail to find key!")
else:
print("index of key is:", indexOfKey)
# binarySearch0823_1 遞歸實(shí)現(xiàn)
def binarySearch(inputArray, low, high, key):
# low high mid
if low <= high :
mid = low + (high - low) // 2
if inputArray[mid] > key:
return binarySearch(inputArray, low, mid - 1, key)
elif inputArray[mid] < key:
return binarySearch(inputArray, mid + 1, high, key)
else:
return mid
return 0
if __name__ == "__main__":
inputArray = [0, 1, 2, 3, 5, 12, 12, 12, 15, 29, 55] #其中，下標(biāo)為0的位置不參與查找
lenOfArray = len(inputArray) - 1
indexOfKey = binarySearch(inputArray, 1, lenOfArray, 15)
if indexOfKey == 0:
print("fail to find key!")
else:
print("index of key is:", indexOfKey)
最好時(shí)間復(fù)雜度: O(1)---在第一個(gè)中間位置就找到key
最壞時(shí)間復(fù)雜度：O(log2^n+1) = O(log2^n) ---一直查找到二叉樹的葉子節(jié)點(diǎn)才找到或者遍歷到葉子節(jié)點(diǎn)發(fā)現(xiàn)無(wú)記錄
3. 哈希表查找
無(wú)論是順序表查找，還是二分查找，都需要使用待查找關(guān)鍵字key與數(shù)組元素比較，然后一步步縮小查找范圍，從而查找到key。哈希表查找避免了“比較”的步驟，可以直接通過關(guān)鍵字key得到待查找記錄的內(nèi)存存儲(chǔ)位置（即下標(biāo)）。
關(guān)鍵字k與記錄的存儲(chǔ)位置之間的對(duì)應(yīng)關(guān)系稱為散列函數(shù)（又稱哈希函數(shù)）。利用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表。
散列技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。散列技術(shù)的記錄之間不存在邏輯關(guān)系，記錄只與關(guān)鍵字有關(guān)系。
常用的幾種散列函數(shù)構(gòu)造方法：
1). 直接定址法。散列函數(shù)為線性函數(shù) hash = a * key + b (a, b為常數(shù)) --適合查找表較小且連續(xù)的情況
2). 數(shù)字分析法。抽取關(guān)鍵字的一部分來(lái)計(jì)算散列存儲(chǔ)位置 --適合于關(guān)鍵字位數(shù)比較大的情況
3). 平方取中法。 對(duì)關(guān)鍵字取平方，并抽取中間n位作為散列地址 --適合于不知道關(guān)鍵字分布，且位數(shù)不是很大的情況
4). 折疊法。將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（若最后面一部分位數(shù)不夠可以與其他位數(shù)不相等），然后將這幾部分疊加求和，并按照散列表表長(zhǎng)，取后幾位作為散列地址。 --適合關(guān)鍵字位數(shù)比較大的情況
5). 除留余數(shù)法。f(key) = key mod p (p <= m), m為散列表長(zhǎng)
6). 隨機(jī)數(shù)法。--若關(guān)鍵字長(zhǎng)度不等，可采用此方法
若兩個(gè)關(guān)鍵字key1 != key2, 而通過上面的散列函數(shù)構(gòu)造方法得到的f(key1) == f(key2)，即發(fā)生了沖突，此時(shí)key1, key2稱為散列函數(shù)的同義詞，那么可以采用以下方法來(lái)處理沖突。
1). 開放定址法。一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址。即：fi(key) = (f(key) + di) mod m (di = 1,2,3,...,m-1); 其中fi(key)是處理沖突后，給關(guān)鍵字key賦予的空散列地址。f(key)是通過上面六種構(gòu)造方法計(jì)算得到的散列地址。 m為散列表表長(zhǎng)。
2). 再散列函數(shù)法。事先準(zhǔn)備多個(gè)散列函數(shù)，每當(dāng)有散列地址沖突時(shí)，就換一個(gè)散列函數(shù)計(jì)算。
3). 鏈地址法。將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表里，單鏈表稱為同義詞子表，散列表中只存儲(chǔ)所有同義詞子表的頭指針。
4). 公共溢出區(qū)法。為所有沖突的關(guān)鍵字建立一個(gè)公共溢出區(qū)存放。查找時(shí)，對(duì)于給定關(guān)鍵字key，先通過散列函數(shù)計(jì)算出散列地址，與基本表相應(yīng)位置比對(duì)，若相等則查找成功；若不相等，則到溢出表按順序查找。
代碼
#hashSearch.py
#使用除留余數(shù)法實(shí)現(xiàn)的哈希函數(shù)
def hash(key, hashLen):
return key % hashLen
#插入關(guān)鍵字進(jìn)散列表
def insertHash(hashTable, hashLen, key):
hashAddr = hash(key, hashLen) #通過哈希函數(shù)求散列地址
#如果字典hashTable中的key已經(jīng)存在，說明發(fā)生了沖突，這里采用開放尋址法解決沖突
while hashTable.get(hashAddr):
hashAddr += 1
hashAddr = hash(hashAddr, hashLen) #開放地址法解決沖突：f1(key) = (f(key) + di) % hashLen
hashTable[hashAddr] = key
#從散列表中查詢關(guān)鍵字key
def searchHash(hashTable, hashLen, key):
hashAddr = hash(key, hashLen)
# 若字典hashTable中的key已經(jīng)存在并且key對(duì)應(yīng)的value與待查詢關(guān)鍵字key不相等，說明發(fā)生了沖突，同樣采用開放地址法解決沖突
while hashTable.get(hashAddr) and hashTable[hashAddr] != key:
hashAddr += 1
hashAddr = hash(hashAddr, hashLen)
if hashTable.get(hashAddr) == None:
return None
return hashAddr
if __name__ == "__main__":
hashLen = 20
L = [13, 29, 27, 28, 26, 30, 38]
hashTable = {}
for i in L:
insertHash(hashTable, hashLen, i)
searchResult = searchHash(hashTable, hashLen, 13)
if searchResult == None:
print("no this record!")
else:
print("index of key is:",searchResult)
若沒有·沖突，則散列查找時(shí)間復(fù)雜度為O(1). 不管記錄數(shù)n有多大，總可以選擇一個(gè)合適的裝填因子(裝填因子 = 填入表中的記錄個(gè)數(shù)/散列表長(zhǎng)度)，將平均查找長(zhǎng)度限定在某一個(gè)范圍內(nèi)，此時(shí)散列查找的時(shí)間復(fù)雜度即可一直保持在O(1).
4. 二叉排序樹查找
5. 平衡二叉樹(AVL樹)查找
6. 多路查找樹(B樹)查找
這三個(gè)有關(guān)于樹的查找，參考另一篇文章：完全二叉樹 平衡二叉樹 二叉查找樹 B樹 B+樹
