リスト全体ではなくバイナリ検索の通過リストスライス

Question

リスト全体の代わりにリストスライスを渡すと、このリストのバイナリ検索が高速化しますか？リストには何百万ものアイテムがありますか？通常

：

def binary_search(data, target, low, high): 
if low > high: 
    return False 
else: 
    mid = (low + high) // 2 
    if target == data[mid]: 
     return True 
    elif target < data[mid]: 
     return binary_search(data[low:mid-1], target, 0, mid) 
    else: 
     return binary_search(data[mid+1:high], target, 0, high-mid) 

私は現在、これがあれば、私は本当に知らないので、アルゴリズムについて学んでいます：リストのスライスに

def binary_search(data, target, low, high): 
if low > high: 
    return False 
else: 
    mid = (low + high) // 2 
    if target == data[mid]: 
     return True 
    elif target < data[mid]: 
     return binary_search(data, target, low, mid-1) 
    else: 
     return binary_search(data, target, mid+1, high) 

（私はそれを少し変更する必要がありました）ベストプラクティスかどうか。

Answer 1

私は第二のアプローチでTimeComplexityは通常のバイナリ検索と同じですが、Space complexityが増加不要だと思います。..

あなたの最初のバイナリ検索アルゴリズムによって取られた空間が同じであることを意味し、O(1) space定数とり配列内の任意の数の要素に対して しかし、2番目のケースでは、空間の複雑さはO（logn）によって増加する必要はないので、非効率的です。

Answer 2

第二のアプローチに伴う問題は、そのようなスライシング手段元のリストから各反復で別のlistオブジェクトを作成することである：

• メモリ割り当て
• メモリコピー元のリストから

したがって、索引付けはより明確になるかもしれませんが、パフォーマンスは実際に低下し、検索された効果の逆になります。