Recherche binaire en Python

Question

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

J'ai trouvé les fonctions bisect_left/droite dans le traversent, module, mais ils ont encore de retour d'un poste, 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 pas (ne veux pas insérer quoi que ce soit).

J'ai pensé à l'aide d' bisect_left , puis de vérifier si l'élément à cette position est égale à ce que je cherche, mais qui semble lourd (et j'ai aussi besoin de faire la vérification des limites si le nombre peut être plus grand que le plus grand nombre dans ma liste). Si il y a une meilleure méthode, je voudrais savoir à ce sujet.

Edit Pour préciser ce que j'en ai besoin pour: je suis conscient qu'un dictionnaire serait très bien adapté pour cela, mais j'essaie de garder la mémoire de la consommation aussi faible que possible. Mon usage prévu serait une sorte de double sens (look-up table. J'ai dans la table d'une liste de valeurs et j'ai besoin d'être en mesure d'accéder à des valeurs en fonction de 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'aide d'un dictionnaire car ce serait le moyen le plus rapide, mais serait environ le double de la mémoire.

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

Answer 1

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

Answer 2

Pourquoi ne pas regarder le code pour bisect_left/droite et adaptez-la en fonction de votre objectif.

Comme ça :

Answer 3

C'est un peu hors-sujet (depuis Moe réponse semble complet à l'OP de la question), mais il pourrait être intéressant de regarder la complexité de votre ensemble de la procédure de bout en bout. Si vous êtes à la stocker dans un listes triées (qui est l'endroit où une binaire de la recherche de l'aide), et puis il suffit de vérifier l'existence, vous êtes engager (dans le pire des cas, sauf indication):

Trier Les Listes

• O( n log n) pour la création de la liste (si c'est des données non triées. O(n), si c'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) O(log n) en moyenne cas, selon votre modèle)

Alors qu'avec un set(), vous êtes encourir

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

La chose une liste triée devient vraiment vous êtes "suivant", "précédent" et "plages" (y compris l'insertion ou la suppression des plages), qui sont en O(1) O(|gamme|), un indice de départ. Si vous n'utilisez pas ces sortes d'opérations souvent, puis les stocker sous la forme d'ensembles et de tri pour l'affichage pourrait être une meilleure affaire ensemble. set() subit très peu de charge supplémentaire en python.

Answer 4

Il pourrait être utile de mentionner que les docs de Bissect fournissent maintenant des exemples recherche : http://docs.python.org/library/bisect.html#searching-sorted-lists

(Raising ValueError au lieu de retourner -1 ou aucun n’est plus Pythonique-list.index() t-il, par exemple. « Mais bien sûr, vous pouvez adapter les exemples à vos besoins).

Answer 5

Plus simple est d’utiliser coupent et vérifier une position arrière pour voir si la question est là :