Recherche binaire (bisection) en Python

est-il une fonction de bibliothèque qui effectue une recherche binaire sur une liste/tuple et renvoie la position de l'élément s'il est trouvé et 'False' (-1, None, etc.) si pas?

j'ai trouvé les fonctions bisect_left/right dans le module bisect , mais elles renvoient quand même une position même si l'élément n'est pas dans la liste. C'est parfaitement correct pour leur usage prévu, mais je veux juste savoir si un article est dans la liste ou pas (ne veut pas insérer quoi que ce soit).

j'ai pensé à utiliser bisect_left et ensuite vérifier si l'élément à cette position est égale à ce que je cherche, mais cela semble encombrant (et je dois également faire la vérification des limites si le nombre peut être plus grand que le plus grand nombre dans ma liste). S'il y a une meilleure méthode, j'aimerais la connaître.

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

L'utilisation d'un dictionnaire pour cela serait le moyen le plus rapide, mais serait (approximativement) le double des besoins de mémoire.

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

157
demandé sur Mateusz Piotrowski 2008-10-17 18:23:17

20 réponses

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
213
répondu Dave Abrahams 2017-02-22 15:01:53

pourquoi ne pas regarder le code pour bisect_left / right et l'adapter à votre but.

comme ceci:

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
54
répondu Moe 2012-05-14 06:29:13

C'est un peu hors sujet (puisque la réponse de Moe semble complète à la question de L'OP), mais il pourrait être intéressant d'examiner la complexité pour l'ensemble de votre procédure de bout en bout. Si vous stockez quelque chose dans des listes triées (ce qui est où une recherche binaire serait utile), et puis juste vérifier l'existence, vous encourez (le pire des cas, à moins que spécifié):

Listes Triées

  • O (N log n) À initialement créer la liste (si ce sont des données non triées. O (n), si elle est triée )
  • O( log n) recherches (c'est le binaire de recherche de la partie)
  • O (n ) Insérer / Supprimer(peut-être O(1) ou o (log n) CAS moyen, selon votre modèle)

alors qu'avec une set() , 151930920"

  • O(n) pour créer
  • O(1) recherche
  • O (1) Insérer / Supprimer

la chose qu'une liste triée obtient vraiment est "next", "previous", et "ranges" (y compris l'insertion ou la suppression de ranges), qui sont O(1) ou O(|range|), avec un index de départ. Si vous n'utilisez pas souvent ce genre d'opération, alors stocker en tant que sets, et trier pour affichage pourrait être une meilleure affaire dans l'ensemble. set() engage très peu de frais généraux supplémentaires en python.

36
répondu Gregg Lind 2012-04-03 14:41:13

il pourrait être intéressant de mentionner que les docs de bisect fournissent maintenant des exemples de recherche: http://docs.python.org/library/bisect.html#searching-sorted-lists

(collecte de ValueError au lieu de retourner -1 ou Aucune ne l'est plus pythonic – liste.index (), par exemple. Mais vous pouvez bien sûr adapter les exemples à vos besoins.)

12
répondu Petr Viktorin 2011-04-23 08:36:45

le plus simple est d'utiliser bisect et de vérifier une position en arrière pour voir si l'article 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
11
répondu Imran 2010-06-30 03:01:31

d'après le manuel:

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

8.5.1. Recherche De Listes Triées

les fonctions de bisect() ci-dessus sont utiles pour trouver des points d'insertion mais peuvent être délicates ou difficiles à utiliser pour des tâches de recherche courantes. Les cinq fonctions suivantes montrent comment les transformer en une recherche 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
7
répondu arainchi 2013-12-29 17:20:44

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.

De la docs bisect.bisect_left(a, x, lo=0, hi=len(a))

le module bisection n'exige pas que le tableau de recherche soit précalculé à l'avance. Vous pouvez simplement présenter les endpoints au bisect.bisect_left au lieu de cela en utilisant les valeurs par défaut de 0 et len(a) .

encore plus important pour mon usage, à la recherche d'une valeur X telle que l'erreur d'une fonction donnée est 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.

il suffit de fournir un objet qui définit __getitem__ comme a

Par exemple, nous pourrions utiliser la traversent, l'algorithme 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)
6
répondu paulluap 2017-05-23 11:54:43

si vous voulez juste voir si elle est présente, essayez de transformer la liste en 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.

4
répondu jrb 2008-10-17 15:03:30

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
2
répondu Florent 2013-09-07 22:08:09

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 cela est le même avantage que la plupart du code de bibliothèque a - il est très performant, bien testé et fonctionne juste (recherches binaires en particulier peut être assez difficile à mettre en œuvre avec succès - en particulier si les cas de bord ne sont pas soigneusement considérés).

Types De Base

pour les types de base comme les chaînes ou les ints c'est assez facile - tout ce dont vous avez besoin est le module bisect 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 utiliser ceci pour trouver 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']

évidemment, vous pouvez simplement retourner l'indice plutôt que la valeur à cet indice si vous le souhaitez.

objets

pour les types personnalisés ou les objets, les choses sont un peu plus compliquées: vous devez vous assurer d'implémenter des méthodes de comparaison riches pour obtenir bisect 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 dans au moins Python 2.7 - > 3.3

2
répondu stephenfin 2013-11-15 18:03:48

celui-ci est:

  • non récursive (ce qui le rend plus efficace de la mémoire que la plupart des récursive approches)
  • effectivement de travail
  • fast car s'exécute sans inutiles si et "conditions 151960920"
  • basé sur une assertion mathématique que le étage d' (bas + haut)/2 est toujours plus petit que haute faible est la limite inférieure et haute est la limite supérieure.
  • testé: d

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
2
répondu Mateusz Piotrowski 2016-01-17 23:30:55

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, puisque 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 fois. Cela fait-il une différence pour vous? Et de combien d'articles parle-t-on?

1
répondu Kirk Strauser 2008-10-17 21:01:17

ce code fonctionne avec des listes entières de manière récursive. Recherche le scénario le plus simple, qui est: longueur de la liste inférieure à 2. Cela signifie que la réponse est déjà là et qu'un test est effectué pour vérifier la bonne réponse. Si ce n'est pas le cas, une valeur moyenne est définie et testée pour être correcte, si ce n'est pas la section est effectuée en appelant à nouveau la fonction, mais en définissant la valeur moyenne comme la limite supérieure ou inférieure, en la déplaçant vers la gauche ou la droite

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) &lt 2:
        return intList[lowValue] == intValue or intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    if intList[middleValue] == intValue:
        return True
    if intList[middleValue] > intValue:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)
1
répondu rct 2012-04-30 21:49:00

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
1
répondu jdsantiagojr 2013-10-10 00:02:51
'''
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. veuillez me corriger :) . Merci

0
répondu iraycd 2012-05-11 17:02:27
  • s est une liste.
  • binary(s, 0, len(s) - 1, find) est l'appel initial.
  • la fonction retourne un index de l'article demandé. 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)
    
0
répondu AV94 2016-01-12 00:05:04
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
0
répondu user3412550 2017-05-18 00:41:57

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)

// appel de fonction ci-dessus :

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))
0
répondu jitesh mohite 2017-06-26 13:43:58

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 à 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 utiliser cette.

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
0
répondu sonus21 2017-07-12 16:26:14

beaucoup de bonnes solutions ci-dessus, mais je n'ai pas vu une simple (KISS keep it simple (cause i'm) utilisation stupide du Python construit dans/generic fonction bisect pour faire une recherche binaire. Avec un peu de code autour de la fonction bisect, je pense que j'ai un exemple ci-dessous où j'ai testé tous les cas pour un petit tableau de noms de chaîne. Certaines des solutions ci-dessus font allusion à/disent ceci, mais espérons que le code simple ci-dessous aidera n'importe qui confus comme je l'étais.

Python traversent, est utilisé pour indiquer où insérer une nouvelle valeur/objet de recherche dans une liste triée. Le code ci-dessous qui utilise bisect_left qui retournera l'index du hit si l'élément de recherche dans la liste/tableau est trouvé (note bisect et bisect_right retourneront l'index de l'élément après le hit ou le match comme point d'insertion) si non trouvé, bisect_left retournera un index à 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 fin de la liste où l'index retourné serait au-delà de la fin de la liste/tableau, et qui dans le code au-dessous de la sortie précoce par 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
0
répondu Bob 2018-04-18 19:15:07