查找一般要掌握順序查找、二分查找泊愧、哈希表查找和二叉排序樹(shù)查找。要能夠快速準(zhǔn)確地寫出二分查找的代碼盛正。
1. 順序查找
順序查找就是按照順序表删咱，一個(gè)一個(gè)問(wèn)哎是不是你是不是你，不是就繼續(xù)問(wèn)下一個(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 # 從查找表的末元素開(kāi)始向前查找
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開(kāi)始，主要是存儲(chǔ)數(shù)據(jù)從1開(kāi)始惭每，下標(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ǔ)的原因是：查找過(guò)程會(huì)對(duì)下標(biāo)進(jìn)行操作钙勃，而鏈?zhǔn)酱鎯?chǔ)只能通過(guò)p->next的形式尋找后面的元素，無(wú)法對(duì)下標(biāo)進(jìn)行操作聂喇。
查找過(guò)程
首先辖源，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較希太，如果兩者相等克饶，則查找成功；否則利用中間位置記錄將表分成前誊辉、后兩個(gè)子表矾湃，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表堕澄，否則進(jìn)一步查找后一子表邀跃。重復(fù)以上過(guò)程，直到找到滿足條件的記錄蛙紫，使查找成功拍屑，或直到子表不存在為止，此時(shí)查找不成功坑傅。
算法時(shí)間復(fù)雜度
O(log2^n) #是以2為底僵驰，n的對(duì)數(shù)
對(duì)于二分查找的時(shí)間復(fù)雜度，可以將其映射為二叉樹(shù)裁蚁。最多查找次數(shù)不超過(guò)二叉樹(shù)的深度即log(2 ^ n)+1（對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)矢渊，其深度為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) ---一直查找到二叉樹(shù)的葉子節(jié)點(diǎn)才找到或者遍歷到葉子節(jié)點(diǎn)發(fā)現(xiàn)無(wú)記錄
3. 哈希表查找
無(wú)論是順序表查找，還是二分查找室谚，都需要使用待查找關(guān)鍵字key與數(shù)組元素比較毡鉴，然后一步步縮小查找范圍，從而查找到key秒赤。哈希表查找避免了“比較”的步驟猪瞬，可以直接通過(guò)關(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, 而通過(guò)上面的散列函數(shù)構(gòu)造方法得到的f(key1) == f(key2)，即發(fā)生了沖突婆誓，此時(shí)key1, key2稱為散列函數(shù)的同義詞吃环，那么可以采用以下方法來(lái)處理沖突。
1). 開(kāi)放定址法洋幻。一旦發(fā)生了沖突郁轻，就去尋找下一個(gè)空的散列地址。即：fi(key) = (f(key) + di) mod m (di = 1,2,3,...,m-1); 其中fi(key)是處理沖突后文留，給關(guān)鍵字key賦予的空散列地址好唯。f(key)是通過(guò)上面六種構(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吁断，先通過(guò)散列函數(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) #通過(guò)哈希函數(shù)求散列地址
#如果字典hashTable中的key已經(jīng)存在，說(shuō)明發(fā)生了沖突炎咖，這里采用開(kāi)放尋址法解決沖突
while hashTable.get(hashAddr):
hashAddr += 1
hashAddr = hash(hashAddr, hashLen) #開(kāi)放地址法解決沖突：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不相等赃泡，說(shuō)明發(fā)生了沖突，同樣采用開(kāi)放地址法解決沖突
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)
若沒(méi)有·沖突绸栅，則散列查找時(shí)間復(fù)雜度為O(1). 不管記錄數(shù)n有多大级野，總可以選擇一個(gè)合適的裝填因子(裝填因子 = 填入表中的記錄個(gè)數(shù)/散列表長(zhǎng)度)，將平均查找長(zhǎng)度限定在某一個(gè)范圍內(nèi)粹胯，此時(shí)散列查找的時(shí)間復(fù)雜度即可一直保持在O(1).
4. 二叉排序樹(shù)查找
5. 平衡二叉樹(shù)(AVL樹(shù))查找
6. 多路查找樹(shù)(B樹(shù))查找
這三個(gè)有關(guān)于樹(shù)的查找蓖柔，參考另一篇文章：完全二叉樹(shù) 平衡二叉樹(shù) 二叉查找樹(shù) B樹(shù) B+樹(shù)
