python実装二分検索およびbisectモジュールの概要

検索ではpythonにlistがあります.index()の方法.

<span style="font-size:14px;">>>> a=[2,4,1,9,3]           #list     ，      
>>> a.index(4)              #        list    
1</span>

これはpythonにおける基本的な検索方法であり、簡単であるが、時間的複雑度がO(n)であるため、大規模なクエリーには不十分である可能性がある.二分検索は代替方法です.
二分検索のオブジェクトは、整列配列です.この点は特に注意が必要だ.
アルゴリズムの基本手順:1.配列の中間要素から始まり、中間要素がちょうど検索する要素であれば、検索プロセスは終了します.2.ある特定の要素が中間要素より大きいか小さい場合、配列が中間要素より大きいか小さいかの半分で検索され、最初と同じように中間要素から比較されます.3.あるステップで配列が空の場合は、見つからないことを意味します.この検索アルゴリズムは、比較のたびに検索範囲を半分に縮小します.時間複雑度:O(logn)
以下に2つの実装方法があり、1つは再帰であり、もう1つはwhileサイクル制御である.

def binarySearch1(lst,value,low,high):
    if high < low:
        return -1
    mid = (low+high)/2
    if lst[mid]>value:
        return binarySearch1(lst,value,low,mid-1)
    elif lst[mid]<value:
        return binarySearch1(lst,value,mid+1,high)
    else:
        return mid
def binarySearch2(lst,value):
    low,high = 0,len(lst)-1
    while low<=high:
        mid = (low+high)/2
        if lst[mid]<value:
            low = mid + 1
        elif value<lst[mid]:
            high = mid - 1
        else:
            return mid
    return -1

if __name__ == '__main__':
    l = range(50)
    print binarySearch1(l,10,0,49)
    print binarySearch2(l,10)

python標準ライブラリにはbisectというグレーの常給力モジュールがあります.このライブラリは秩序あるシーケンスを受け入れ,内部実装は二分である.

import bisect

def binarySearch3(lst,x):
    i = bisect.bisect_left(lst,x)
    if i != len(lst) and lst[i] == x:
        return i
    raise ValueError

if __name__ == '__main__':
    lst = sorted([2,5,2,7,3])
    print binarySearch3(lst,5)