搜索
? ? ? ?搜索是在一個(gè)項(xiàng)目集合中找到一個(gè)特定項(xiàng)目的算法過程。搜索通常的答案是真的或假的捉撮，因?yàn)樵擁?xiàng)目是否存在驮宴。搜索的幾種常見方法：順序查找、二分法查找呕缭、二叉樹查找堵泽、哈希查找。
搜索二分法查找
? ? ? ?二分查找又稱折半查找恢总，優(yōu)點(diǎn)是比較次數(shù)少迎罗，查找速度快，平均性能好片仿；其缺點(diǎn)是要求待查表為有序表纹安，且插入刪除困難。因此砂豌，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表厢岂。首先，假設(shè)表中元素是按升序排列阳距，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較塔粒，如果兩者相等，則查找成功筐摘；否則利用中間位置記錄將表分成前卒茬、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字咖熟，則進(jìn)一步查找前一子表圃酵，否則進(jìn)一步查找后一子表。重復(fù)以上過程馍管，直到找到滿足條件的記錄郭赐，使查找成功，或直到子表不存在為止确沸，此時(shí)查找不成功捌锭。
image.png
二分法查找實(shí)現(xiàn)
（非遞歸實(shí)現(xiàn)）
def binary_search(alist,item):
first = 0
last = len(alist) - 1
while first <= last:
midpoint = (first + last)//2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint + 1
return False
testlist = [0,1,2,8,13,17,19,32,42]
print(binary_search(testlist,3))
print(binary_search(testlist,13))
（遞歸實(shí)現(xiàn)）
def binary_search(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint] == item:
return True
else:
if item<alist[midpoint]:
return binary_search(alist[:midpoint],item)
else:
return binary_search(alist[midpoint+1:],item)
testlist = [0,1,2,8,13,17,19,32,42]
print(binary_search(testlist,3))
print(binary_search(testlist,13))
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O（1）
最壞時(shí)間復(fù)雜度：O（logn）
