liste passage de recherche binaire tranche au lieu de la liste entière

Question

est cette recherche binaire de la liste triée va être plus rapide si nous passons une tranche de liste au lieu de la liste, où la liste a des millions d'articles?

normal:

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) 

Avec tranche de liste (je devais modifier un peu):

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) 

Je suis en train d'apprendre sur les algorithmes, donc je ne sais vraiment pas si cela est meilleure pratique ou non.

Answer 1

Je pense que la deuxième approche, le TimeComplexity est la même que normal binaire Search mais Space complexity est inutile de plus en plus ..

Votre première recherche binaire prend O(1) space constante, ce qui signifie que l'espace occupé par l'algorithme est le même pour n'importe quel nombre d'éléments dans le tableau. Mais dans votre deuxième complexité de l'espace de cas est inutile augmenté de O (logn) d'où il est inefficace.

Answer 2

le problème avec la seconde approche est que cette découpe crée un autre objet list à chaque itération de la liste initiale qui signifie:

• allocation de mémoire
• copie de la mémoire de liste d'origine

Ainsi, l'indexation peut devenir plus claire, mais les performances sont en réalité dégradées, ce qui entraîne l'inverse de l'effet recherché.