APP
有序查找，無(wú)序查找，二分查找總結(jié)
基本排序方法：
- ??無(wú)序查找??
- ??有序查找??
- ??二分查找??
無(wú)序查找
其實(shí)大部分的查找方法，都是通過(guò)先定義初始的 found=False，然后一旦查找到之后，found變?yōu)門(mén)rue：
def sequential(alist,item):
pos=0
found=False
while pos<len(alist) and not found:
if alist[pos]==item:
found=True
else:
pos=pos+1
return found
print(sequential([1,3,5],2))
有序查找
在最好的情況下，有序查找只需要比較一次就能知道目標(biāo)元素不在列表中，平均情況下需要比較n/2次，不過(guò)算法的復(fù)雜度仍然是O（n）。總之，只有當(dāng)列表中不存在目標(biāo)元素時(shí)，有序查找才會(huì)提高查找的速率。
def youxu(alist,item):
pos=0
found=False
stop=False
while pos<len(alist) and not found and not stop:
if alist[pos]==item:
found=True
else:
if alist[pos]>item:
stop=True
else:
pos=pos+1
return found
print(youxu([1,3,5,7],3))
二分查找
先從中間查找，如果目標(biāo)元素大，則在右面找；反之在左邊找：
def erfenchazhao(alist,item):
first=0
last=len(alist)-1
found=False
while first <=last and not found:
midpoint=(first+last)//2
print(midpoint)
if alist[midpoint] == item:
found = True
else:
if item<alist[midpoint]:
last =midpoint -1
else:
first=midpoint+1
return found
print(erfenchazhao([1,5,6,7,9],5))
本文摘自 ：https://blog.51cto.com/u
