Algorithme de recherche binaire en python

Je suis en train de mettre en œuvre les binaires de recherche en python et de l'avoir écrit comme suit. Cependant, je ne peux pas le faire arrêter à chaque fois que needle_element est plus grand que le plus grand élément dans le tableau.

Pouvez-vous aider? Merci.

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"

source d'informationauteur AbdulFattah Popoola | 2012-02-29

  1. 8

    Dans le cas que needle_element > array[mid]vous actuellement passer array[mid:] de l'appel récursif. Mais vous savez que array[mid] est trop petit, de sorte que vous pouvez passer array[mid+1:] à la place (et d'ajuster le retour de l'index en conséquence).

    Si l'aiguille est plus grand que tous les éléments dans le tableau, faisant de cette façon vous donnera par la suite un tableau vide, et une erreur est signalée comme prévu.

    Remarque: la Création d'un sous-tableau à chaque fois, de mauvaises performances pour les grands tableaux. C'est mieux de passer dans les limites du tableau à la place.

  2. 11

    Il serait beaucoup mieux de travailler avec un lower et upper index Lasse V. Karlsen a été suggéré dans un commentaire à la question.

    Ce serait le code:

    def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x
    • lower < upper va s'arrêter une fois que vous avez atteint le plus petit nombre (à partir de la gauche)
    • if lower == x: break va s'arrêter une fois que vous avez atteint le nombre le plus élevé (à partir de la droite)

    Exemple:

    >>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None
  3. 6

    tableau[mi:] crée un nouveau sous-copier à chaque fois que vous l'appelez = lent. Aussi, vous utiliser la récursivité, qui en Python est lent, trop.

    Essayez ceci:

    def binarysearch(sequence, value):
    lo, hi = 0, len(sequence) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sequence[mid] < value:
            lo = mid + 1
        elif value < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None
  4. 4

    Pourquoi ne pas utiliser le traversent, le module? Il devrait faire le travail vous avez besoin d'---moins de code pour vous à maintenir et à tester.

  5. 2

    Vous pouvez améliorer votre algorithme, comme les autres l'ont suggéré, mais nous allons d'abord examiner pourquoi il ne fonctionne pas:

    Vous êtes coincé dans une boucle car si needle_element > array[mid]vous êtes, y compris l'élément de mid dans la traversée de la matrice de vous chercher ensuite. Donc, si l'aiguille n'est pas dans le tableau, vous finirez par être à la recherche d'un tableau de longueur pour toujours. Passer array[mid+1:] à la place (c'est légal, même si mid+1 n'est pas un index valide), et vous finirez par appel de votre fonction avec un tableau de longueur zéro. Donc len(array) == 0 signifie "pas trouvé", pas une erreur. Gérer de manière appropriée.

  6. 0

    Si vous faites une recherche binaire, je suppose que le tableau est trié. Si c'est vrai, vous devriez être en mesure de comparer le dernier élément du tableau à la needle_element. Comme le poulpe dit, cela peut être fait avant que la recherche commence.

  7. 0

    Vous pouvez juste vérifier que needle_element est dans les limites du tableau avant de commencer à tous. Ce sera plus efficace aussi, puisque vous n'aurez pas à faire plusieurs étapes pour arriver à la fin.

    if needle_element < array[0] or needle_element > array[-1]:
    # do something, raise error perhaps?
  8. 0

    Toutes les réponses ci-dessus sont vraies , mais je pense qu'il serait bon de partager mon code 

    def binary_search(number):
numbers_list = range(20, 100)
i = 0
j = len(numbers_list)
while i < j:
    middle = int((i + j) / 2)
    if number > numbers_list[middle]:
        i = middle + 1
    else:
        j = middle
return 'the index is '+str(i)
  9. 0

    Il renvoie l'index de la clé dans le tableau en utilisant récursive.

    round() est une fonction de convertir des float en entier et dont le code est rapide et va de cas attendus[O(logn)].

    A=[1,2,3,4,5,6,7,8,9,10]
low = 0
hi = len(A)
v=3
def BS(A,low,hi,v):
    mid = round((hi+low)/2.0)
    if v == mid:
        print ("You have found dude!" + " " + "Index of v is ", A.index(v))
    elif v < mid:
        print ("Item is smaller than mid")
        hi = mid-1
        BS(A,low,hi,v)
    else :
        print ("Item is greater than mid")
        low = mid + 1
        BS(A,low,hi,v)
BS(A,low,hi,v)
  10. 0

    Sans inférieure/supérieure de l'index, cela devrait également faire:

    def exists_element(element, array):
    if not array:
        yield False

    mid = len(array) // 2
    if element == array[mid]:
        yield True
    elif element < array[mid]:
        yield from exists_element(element, array[:mid])
    else:
        yield from exists_element(element, array[mid + 1:])
  11. 0
    def binary_search(array, target):
    low = 0
    mid = len(array) / 2
    upper = len(array)

    if len(array) == 1:
        if array[0] == target:
            print target
            return array[0]
        else:
            return False
    if target == array[mid]:
        print array[mid]
        return mid
    else:
        if mid > low:
            arrayl = array[0:mid]
            binary_search(arrayl, target)

        if upper > mid:
            arrayu = array[mid:len(array)]
            binary_search(arrayu, target)

if __name__ == "__main__":
    a = [3,2,9,8,4,1,9,6,5,9,7]
    binary_search(a,9)
  12. 0

    En Utilisant La Récursivité:

    def binarySearch(arr,item):
    c = len(arr)//2
    if item > arr[c]:
       ans = binarySearch(arr[c+1:],item)
       if ans:
          return binarySearch(arr[c+1],item)+c+1
    elif item < arr[c]:
       return binarySearch(arr[:c],item)
    else:
       return c

binarySearch([1,5,8,10,20,50,60],10)
  13. -1

    C'est une queue solution récursive, je pense que c'est plus propre que la copie partielle des tableaux, puis de suivre les indices pour le retour:

    def binarySearch(elem, arr):
    # return the index at which elem lies, or return false
    # if elem is not found
    # pre: array must be sorted
    return binarySearchHelper(elem, arr, 0, len(arr) - 1)

def binarySearchHelper(elem, arr, start, end):
    if start > end:
        return False
    mid = (start + end)//2
    if arr[mid] == elem:
        return mid
    elif arr[mid] > elem:
        # recurse to the left of mid
        return binarySearchHelper(elem, arr, start, mid - 1)
    else:
        # recurse to the right of mid
        return binarySearchHelper(elem, arr, mid + 1, end)