Python検索アルゴリズム

ちくじたんさくほう
n個の要素の中からxの値が存在するかどうかを探して、最初から最後まで1個ずつ最良の情況を探します――第1項は探しているデータの対象で、一回だけ比較が最悪の情況――――――n回の比較が必要で、すべて比較が終わった後で、データの平均情況を調べることができません――比較回数がn/2回のアルゴリズムの時間の複雑度よりO(n)です

def sequentialSearch(alist, item):
    pos=0   #      
    found=False   #       
    while pos

にぶんたんさくほう
プリソートリストの検索リストaの中間位置の項目を検索キーワードtと比較する:等しい場合、検索は成功する;中間項目がtより大きい場合、最初の半分のサブテーブルが検索されます.中間項目がtより小さい場合、検索後の半分のサブテーブルは、条件を満たすレコードが見つかるまで、検索に成功するまで、以上のプロセスを繰り返します.あるいはサブテーブルが存在しない,すなわち検索失敗アルゴリズムの時間的複雑度はO(logn),Nはリスト長である.

def _binarySearch(key,a,lo,hi):   #    
    if hi<=lo:
        return -1   #     ，    
    mid=(lo+hi)//2   #      
    if a[mid]>key:
        return _binarySearch(key,a,lo,mid)
    elif a[mid]

def binarySearch(key,a):   #     
    low=0
    high=len(a)-1
    while low<=high:
        mid=(low+high)//2
        if a[mid]key:
            high=mid-1
        else:
            return mid   #     key a      
    return 'Not found'
    
#test:
alist=[1,3,8,17,29,32]
print binarySearch(3,alist)
#Output:1