Existe-t-il une fonction de bibliothèque qui effectue une recherche binaire sur une liste / un tuple et renvoie la position de l'élément s'il est trouvé et «False» (-1, Aucun, etc.) sinon?

J'ai trouvé les fonctions bisect_left / right dans le module bisect , mais elles renvoient toujours une position même si l'élément n'est pas dans la liste. C'est parfaitement bien pour leur utilisation prévue, mais je veux juste savoir si un élément est dans la liste ou non (je ne veux rien insérer).

J'ai pensé à utiliser bisect_leftpuis à vérifier si l'élément à cette position est égal à ce que je recherche, mais cela semble fastidieux (et j'ai également besoin de vérifier si le nombre peut être supérieur au plus grand nombre de ma liste). S'il y a une meilleure méthode, j'aimerais en savoir plus.

Edit Pour clarifier ce pour quoi j'ai besoin de ceci: je suis conscient qu'un dictionnaire serait très bien adapté pour cela, mais j'essaie de garder la consommation de mémoire aussi faible que possible. Mon utilisation prévue serait une sorte de table de recherche à double sens. J'ai dans le tableau une liste de valeurs et je dois pouvoir accéder aux valeurs en fonction de leur index. Et aussi je veux être en mesure de trouver l'index d'une valeur particulière ou None si la valeur n'est pas dans la liste.

Utiliser un dictionnaire pour cela serait le moyen le plus rapide, mais doublerait (approximativement) les besoins en mémoire.

Je posais cette question en pensant que j'avais peut-être oublié quelque chose dans les bibliothèques Python. Il semble que je devrais écrire mon propre code, comme Moe l'a suggéré.

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Pourquoi ne pas regarder le code de bisect_left / right et l'adapter à vos besoins.

comme ça:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

C'est un peu hors sujet (puisque la réponse de Moe semble complète à la question du PO), mais il pourrait être intéressant d'examiner la complexité de toute votre procédure de bout en bout. Si vous stockez quelque chose dans une liste triée (ce qui est où une recherche binaire aiderait), et que vous vérifiez simplement l'existence, vous encourez (le pire des cas, sauf indication contraire):

Listes triées

• O (n log n) pour créer initialement la liste (si ce sont des données non triées. O (n), si elles sont triées)
• O (log n) recherches (c'est la partie de recherche binaire)
• O (n) insérer / supprimer (peut être une casse moyenne O (1) ou O (log n), selon votre modèle)

Alors qu'avec un set(), vous encourez

• O (n) pour créer
• Recherche O (1)
• O (1) insérer / supprimer

Ce qu'une liste triée vous procure vraiment, ce sont «suivant», «précédent» et «plages» (y compris l'insertion ou la suppression de plages), qui sont O (1) ou O (| plage |), étant donné un index de départ. Si vous n'utilisez pas souvent ce type d'opérations, le stockage en tant qu'ensembles et le tri pour l'affichage pourraient être une meilleure affaire dans l'ensemble. set()n'encourt que très peu de frais généraux supplémentaires en python.

Il peut être intéressant de mentionner que la documentation bisect fournit désormais des exemples de recherche: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Augmenter ValueError au lieu de renvoyer -1 ou None est plus pythonique - list.index () le fait, par exemple. Mais bien sûr, vous pouvez adapter les exemples à vos besoins.)

Le plus simple consiste à utiliser une bissectrice et à cocher une position pour voir si l'élément est là:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

Cela vient du manuel:

http://docs.python.org/2/library/bisect.html

8.5.1. Recherche de listes triées

Les fonctions bisect () ci-dessus sont utiles pour trouver des points d'insertion, mais peuvent être difficiles à utiliser pour les tâches de recherche courantes. Les cinq fonctions suivantes montrent comment les transformer en recherches standard pour les listes triées:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Donc, avec la légère modification, votre code devrait être:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Je suis d'accord que la réponse de @ DaveAbrahams en utilisant le module bisect est la bonne approche. Il n'a pas mentionné un détail important dans sa réponse.

À partir des documents bisect.bisect_left(a, x, lo=0, hi=len(a))

Le module de bissection ne nécessite pas que le tableau de recherche soit précalculé à l'avance. Vous pouvez simplement présenter les points de terminaison à la bisect.bisect_leftplace de celui-ci en utilisant les valeurs par défaut de 0et len(a).

Encore plus important pour mon utilisation, la recherche d'une valeur X telle que l'erreur d'une fonction donnée soit minimisée. Pour ce faire, j'avais besoin d'un moyen pour que l'algorithme de bisect_left appelle mon calcul à la place. C'est vraiment simple.

Fournissez simplement un objet qui définit __getitem__commea

Par exemple, nous pourrions utiliser l'algorithme de bissectrice pour trouver une racine carrée avec une précision arbitraire!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

Si vous voulez juste voir s'il est présent, essayez de transformer la liste en un dict:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

Sur ma machine, "if n in l" a pris 37 secondes, tandis que "if n in d" a pris 0,4 seconde.

Celui-ci est:

• non récursif (ce qui le rend plus efficace en mémoire que la plupart des approches récursives)
• fonctionne réellement
• rapide car il fonctionne sans inutile si son et conditions
• basé sur une affirmation mathématique selon laquelle le plancher de (bas + haut) / 2 est toujours plus petit que haut où bas est la limite inférieure et haut est la limite supérieure.

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

La solution de Dave Abrahams est bonne. Bien que je l'aurais fait minimaliste:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

Bien qu'il n'y ait pas d'algorithme de recherche binaire explicite en Python, il existe un module - bisect- conçu pour trouver le point d'insertion d'un élément dans une liste triée à l'aide d'une recherche binaire. Cela peut être "trompé" en effectuant une recherche binaire. Le plus grand avantage de ceci est le même avantage que la plupart du code de bibliothèque - il est très performant, bien testé et fonctionne juste (les recherches binaires en particulier peuvent être assez difficiles à implémenter avec succès - en particulier si les cas de pointe ne sont pas soigneusement pris en compte).

Types de base

Pour les types de base comme les chaînes ou les entiers, c'est assez facile - tout ce dont vous avez besoin est le bisectmodule et une liste triée:

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

Vous pouvez également l'utiliser pour rechercher des doublons:

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

De toute évidence, vous pouvez simplement renvoyer l'index plutôt que la valeur de cet index si vous le souhaitez.

Objets

Pour les types ou objets personnalisés, les choses sont un peu plus délicates: vous devez vous assurer d'implémenter des méthodes de comparaison riches pour obtenir une bissectrice pour comparer correctement.

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

Cela devrait fonctionner au moins dans Python 2.7 -> 3.3

L'utilisation d'un dict ne voudrait pas doubler votre utilisation de la mémoire à moins que les objets que vous stockez soient vraiment minuscules, car les valeurs ne sont que des pointeurs vers les objets réels:

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

Dans cet exemple, «foo» n'est stocké qu'une seule fois. Cela fait-il une différence pour vous? Et de combien d'articles parlons-nous exactement?

Ce code fonctionne avec des listes d'entiers de manière récursive. Recherche le scénario de cas le plus simple, qui est: longueur de la liste inférieure à 2. Cela signifie que la réponse est déjà là et un test est effectué pour vérifier la bonne réponse. Sinon, une valeur médiane est définie et testée pour être correcte, sinon la bissection est effectuée en appelant à nouveau la fonction, mais en définissant la valeur médiane comme limite supérieure ou inférieure, en la décalant vers la gauche ou la droite

def binary_search (intList, intValue, lowValue, highValue):
    if (highValue - lowValue) <2:
        return intList [lowValue] == intValue ou intList [highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue) / 2)
    if intList [middleValue] == intValue:
        retourne True
    if intList [middleValue]> intValue:
        return binary_search (intList, intValue, lowValue, middleValue - 1)
   return binary_search (intList, intValue, middleValue + 1, highValue)

Consultez les exemples sur Wikipedia http://en.wikipedia.org/wiki/Binary_search_algorithm

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError

'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

Je suppose que c'est beaucoup mieux et efficace. s'il vous plaît corrigez-moi :) . Je vous remercie

• s est une liste.
• binary(s, 0, len(s) - 1, find) est l'appel initial.

• Function renvoie un index de l'élément interrogé. S'il n'y a pas un tel article, il retourne -1.

  def binary(s,p,q,find):
      if find==s[(p+q)/2]:
          return (p+q)/2
      elif p==q-1 or p==q:
          if find==s[q]:
              return q
          else:
              return -1
      elif find < s[(p+q)/2]:
          return binary(s,p,(p+q)/2,find)
      elif find > s[(p+q)/2]:
          return binary(s,(p+q)/2+1,q,find)

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

Recherche binaire :

// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
        print(list)
        print(upperBound)
        print(lowerBound)
        mid = ((upperBound + lowerBound)) // 2
        print(mid)
        if int(list[int(mid)]) == value:
               return "value exist"
        elif int(list[int(mid)]) < value:
             return searchItem(list, value, size, upperBound, mid + 1)
        elif int(list[int(mid)]) > value:
               return searchItem(list, value, size, mid - 1, lowerBound)

// Pour appeler la fonction ci-dessus, utilisez:

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1        
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))

J'avais besoin d'une recherche binaire en python et générique pour les modèles Django. Dans les modèles Django, un modèle peut avoir une clé étrangère vers un autre modèle et je voulais effectuer une recherche sur les objets modèles récupérés. J'ai écrit la fonction suivante, vous pouvez l'utiliser.

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Beaucoup de bonnes solutions ci-dessus, mais je n'ai pas vu une utilisation simple (KISS reste simple (parce que je suis) stupide de la fonction Bissect intégrée / générique de Python pour faire une recherche binaire. Avec un peu de code autour de la fonction Bissect, Je pense avoir un exemple ci-dessous où j'ai testé tous les cas pour un petit tableau de chaînes de noms. Certaines des solutions ci-dessus font allusion à / disent cela, mais j'espère que le code simple ci-dessous aidera n'importe qui dans la confusion comme moi.

Python bisect est utilisé pour indiquer où insérer une nouvelle valeur / élément de recherche dans une liste triée. Le code ci-dessous qui utilise bisect_left qui renverra l'index du hit si l'élément de recherche dans la liste / tableau est trouvé (Notez que bisect et bisect_right renverront l'index de l'élément après le hit ou match comme point d'insertion) Si non trouvé , bisect_left renverra un index vers l'élément suivant dans la liste triée qui ne sera pas == la valeur de recherche. Le seul autre cas est celui où l'élément de recherche irait à la fin de la liste où l'index retourné serait au-delà de la fin de la liste / tableau, et qui dans le code ci-dessous la sortie anticipée de Python avec des poignées logiques "et". (première condition False Python ne vérifie pas les conditions suivantes)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found