Recherche binaire (bissection) en Python

176

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é.

rslite
la source
1
Qu'est-ce que vous essayez d'accomplir? Si les valeurs sont uniques, envisagez d'utiliser un ensemble et "si valeur dans l'ensemble: quelque chose".
Kirk Strauser
Pour ce que ça vaut, "-1" est considéré comme vrai; "0" serait faux.
Glyph
3
J'ai mentionné -1 car une fonction qui renvoie l'index de l'élément recherché dans le tableau peut déjà renvoyer 0, donc -1 est renvoyé si l'élément n'est pas trouvé (similaire à la recherche de sous-chaînes).
rslite
3
Si vous utilisez numpy, np.searchsortedc'est utile. docs.scipy.org/doc/numpy/reference/generated/…
Roman Shapovalov

Réponses:

237
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
Dave Abrahams
la source
10
@volcano Tout comme binsearch en général.
cubuspl42
4
@TomSwirly pas aussi simple que le vôtre mais correct et toujours une amélioration:if hi is None: hi = len(a)
Mark Ransom
Qu'en est-il de l'ordre décroissant?
Parikshit Chalke
2
Pouvez-vous ajouter des explications en dehors du code? Les normes ici ont changé.
SS Anne
54

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
Moe
la source
29
Au départ, j'avais +1, mais maintenant j'en suis venu à la conclusion que ce n'est pas une bonne chose. Si cette réponse est suivie, cela entraînera beaucoup de duplication de code, et comme nous le savons tous, il est vraiment simple de faire une recherche binaire.
abyx
1
ne devrait-il pas être hi = mid - 1dans le elif?
Paweł Prażak
7
@ Paweł: ce sont deux variantes équivalentes, selon que la borne supérieure est inclusive ou exclusive. vous pouvez changer hi = midde hi = mid-1et hi = len(a)en hi = len(a)-1et while lo < hi:en while lo <= hi, et ce serait tout à fait correct
user102008
2
pourquoi ne pas faire quelque chose comme: def binary_search (a, x, lo = 0, hi = None): i = bisect (a, x, lo, hi) return i if a [i] == x else -1 désolé pour le formatage - je ne sais pas comment le faire correctement dans la zone de commentaire
Vitali
1
Vous devriez utiliser bisect.bisect_left()plutôt que cela.
alastair
37

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.

Gregg Lind
la source
7
Il y a une autre chose qu'une liste triée vous procure. O (n) parcours ordonné. Avec un ensemble qui est O (n log n) et vous finissez par avoir à copier les références aux données dans une liste.
Omnifarious
1
Assez vrai! Merci d'avoir développé ce que j'entendais par recherche par plage. Fwiw, un parcours complet est la même chose qu'une requête d'intervalle entre min, max, qui est O (k) où k = n :)
Gregg Lind
14

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.)

Petr Viktorin
la source
11

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
Imran
la source
2
Bien, mais le code barfs si vous ne passez pas la valeur «hi». Je l'écrirais comme ceci: "def binary_search (a, x, lo = 0, hi = None): from bisect import bisect i = bisect (a, x, lo, hi or len (a)) return (i- 1 if a [i-1] == x else -1) "et testez-le comme ceci:" for i in range (1, 20): a = list (range (i)) for aa in a: j = binary_search (a, aa) if j! = aa: print i, aa, j "
hughdbrown
8

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
arainchi
la source
6

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)
paulluap
la source
Ce n'est pas propre. Utilisez scipy.optimizepour cela.
Neil G
4

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.

jrb
la source
2
Ce n'est pas toujours une bonne option pour plusieurs raisons: 1) les dictionnaires / ensembles prennent plus de mémoire. 2) s'il n'a pas grand-chose dans la liste, une recherche binaire peut être plus rapide. 3) la conversion de la liste en dict est une opération O (n) tandis qu'une recherche binaire est O (log n).
Jason Baker
3
En tant que FYI, la surcharge "set" en python par rapport aux listes python, est très très faible. Et ils sont extrêmement rapides pour les recherches. Là où la recherche binaire excelle vraiment, c'est pour rechercher des plages.
Gregg Lind
La conversion de la liste peut être O (n) mais le tri des données dans la liste, ce que vous auriez à faire avant de la rechercher binaire, est pire. D'où viennent les données, vous pouvez probablement les insérer dans un dictionnaire au fur et à mesure. Je conviens que la mémoire peut être un problème.
Mark Baker
4

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 hautbas 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
Mateusz Piotrowski
la source
Pouvez-vous partager les cas de test?
lifebalance
2

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
Florent
la source
2

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

stephenfin
la source
1

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?

Kirk Strauser
la source
C'est une question de nombres et beaucoup d'entre eux :) J'aimerais utiliser un tableau presque aussi grand que la mémoire de l'ordinateur. Je sais que la base de mon problème pourrait être erronée, mais j'étais curieuse de l'absence de méthode de recherche binaire.
rslite
1
Vous ne pouvez pas avoir un objet clé suffisamment petit pour être qualifié de "vraiment petit" ici. Un objet aurait un coût minimum de 3 mots (type, refcount, payload), tandis qu'une liste ajoute 1 mot, un ensemble ajoute 1 mot et un dict ajoute 2 mots. Les trois (list / set / dict) préallouent également l'espace d'une certaine manière, ce qui est un autre multiplicateur, mais toujours pas assez pour avoir de l'importance.
Rhamphoryncus
1

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)
rct
la source
1

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
jdsantiagojr
la source
0
'''
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

iraycd
la source
0
  • 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)
AV94
la source
0
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
user3412550
la source
0

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))
jitsm555
la source
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
sonus21
la source
0

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
Bob
la source