Búsqueda binaria (bisección) en Python

176

¿Existe una función de biblioteca que realiza una búsqueda binaria en una lista / tupla y devuelve la posición del elemento si se encuentra y 'Falso' (-1, Ninguno, etc.) si no?

Encontré las funciones bisect_left / right en el módulo bisect , pero aún así devuelven una posición incluso si el elemento no está en la lista. Eso está perfectamente bien para su uso previsto, pero solo quiero saber si un elemento está en la lista o no (no quiero insertar nada).

Pensé en usar bisect_lefty luego verificar si el elemento en esa posición es igual a lo que estoy buscando, pero eso parece engorroso (y también necesito hacer límites para verificar si el número puede ser mayor que el número más grande en mi lista). Si hay un método mejor, me gustaría saberlo.

Editar Para aclarar para qué necesito esto: soy consciente de que un diccionario sería muy adecuado para esto, pero estoy tratando de mantener el consumo de memoria lo más bajo posible. Mi uso previsto sería una especie de tabla de búsqueda de doble sentido. Tengo en la tabla una lista de valores y necesito poder acceder a los valores en función de su índice. Y también quiero poder encontrar el índice de un valor particular o Ninguno si el valor no está en la lista.

Usar un diccionario para esto sería la forma más rápida, pero (aproximadamente) duplicaría los requisitos de memoria.

Estaba haciendo esta pregunta pensando que podría haber pasado por alto algo en las bibliotecas de Python. Parece que tendré que escribir mi propio código, como sugirió Moe.

rslite
fuente
1
¿Qué es lo que estás tratando de lograr? Si los valores son únicos, considere usar un conjunto y "if value in set: something".
Kirk Strauser
Por lo que vale, "-1" se considera verdadero; "0" sería falso.
Glifo
3
Mencioné -1 porque una función que devuelve el índice del elemento buscado en la matriz ya puede devolver 0, por lo que -1 se devuelve si no se encuentra el elemento (similar a la búsqueda de subcadenas).
rslite
3
Si usas numpy, np.searchsortedes útil. docs.scipy.org/doc/numpy/reference/generated/…
Roman Shapovalov

Respuestas:

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
fuente
10
@volcano También lo hace binsearch en general.
cubuspl42
44
@TomSwirly no es tan simple como el tuyo pero es correcto y sigue siendo una mejora:if hi is None: hi = len(a)
Mark Ransom el
¿Qué pasa con el orden descendente?
Parikshit Chalke
2
¿Puedes agregar alguna explicación fuera del código? Los estándares aquí han cambiado.
SS Anne
54

¿Por qué no mirar el código para bisect_left / right y adaptarlo a su propósito?

Me gusta esto:

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
fuente
29
Originalmente hice +1 en esto, pero ahora he llegado a la conclusión de que esto no es algo bueno. Si se sigue esta respuesta, provocará una gran cantidad de duplicación de código y, como todos sabemos, es realmente simple buscar la búsqueda binaria.
abyx
1
no debería estar hi = mid - 1en el elif?
Paweł Prażak
77
@ Paweł: son dos variantes equivalentes, dependiendo de si el límite superior es inclusivo o exclusivo. puede cambiar hi = mida hi = mid-1y hi = len(a)a hi = len(a)-1y while lo < hi:a while lo <= hi, y sería lo que es equivalente correcta
user102008
2
¿por qué no hacer algo como: def binary_search (a, x, lo = 0, hi = None): i = bisect (a, x, lo, hi) devuelve i si a [i] == x else -1 lo siento por el formato - no estoy seguro de cómo hacer esto correctamente en el área de comentarios
Vitali
1
Deberías usar en bisect.bisect_left()lugar de esto.
alastair el
37

Esto es un poco fuera de tema (ya que la respuesta de Moe parece completa a la pregunta del OP), pero podría valer la pena mirar la complejidad de todo el procedimiento de principio a fin. Si está almacenando algo en una lista ordenada (que es donde una búsqueda binaria ayudaría), y luego solo verificando la existencia, está incurriendo (en el peor de los casos, a menos que se especifique):

Listas ordenadas

  • O (n log n) para crear inicialmente la lista (si se trata de datos sin clasificar. O (n), si está ordenada)
  • O (log n) búsquedas (esta es la parte de búsqueda binaria)
  • O (n) insertar / eliminar (puede ser O (1) u O (log n) caso promedio, dependiendo de su patrón)

Mientras que con un set(), estás incurriendo

  • O (n) para crear
  • O (1) búsqueda
  • O (1) insertar / eliminar

Lo que realmente obtiene una lista ordenada es "siguiente", "anterior" y "rangos" (incluida la inserción o eliminación de rangos), que son O (1) u O (| rango |), dado un índice inicial. Si no está utilizando ese tipo de operaciones con frecuencia, almacenar en conjunto y ordenar para mostrar podría ser una mejor opción en general. set()incurre muy poca sobrecarga adicional en python.

Gregg Lind
fuente
77
Hay otra cosa que te da una lista ordenada. O (n) recorrido ordenado. Con un conjunto que es O (n log n) y terminas teniendo que copiar referencias a los datos en una lista.
Omnifarious
1
¡Suficientemente cierto! Gracias por ampliar lo que quise decir con búsqueda por rango. Fwiw, un recorrido completo es lo mismo una consulta de rango entre min, max, que es O (k) donde k = n :)
Gregg Lind
14

Vale la pena mencionar que los documentos bisectos ahora proporcionan ejemplos de búsqueda: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Elevar ValueError en lugar de devolver -1 o None es más pitónico: list.index () lo hace, por ejemplo. Pero, por supuesto, puede adaptar los ejemplos a sus necesidades).

Petr Viktorin
fuente
11

Lo más simple es usar bisect y verificar una posición hacia atrás para ver si el artículo está allí:

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
fuente
2
Agradable, pero el código barfs si no pasa el valor 'hola'. Lo escribiría así: "def binary_search (a, x, lo = 0, hi = None): desde bisect import bisect i = bisect (a, x, lo, hi o len (a)) return (i- 1 si a [i-1] == x else -1) "y pruébelo así:" para i en rango (1, 20): a = lista (rango (i)) para aa en a: j = binary_search (a, aa) si j! = aa: imprime i, aa, j "
hughdbrown
8

Esto es correcto del manual:

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

8.5.1. Buscar listas ordenadas

Las funciones bisect () anteriores son útiles para encontrar puntos de inserción pero pueden ser difíciles o difíciles de usar para tareas de búsqueda comunes. Las siguientes cinco funciones muestran cómo transformarlas en las búsquedas estándar para listas ordenadas:

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

Entonces, con la ligera modificación, su código debería ser:

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
fuente
6

Estoy de acuerdo en que la respuesta de @ DaveAbrahams utilizando el módulo bisect es el enfoque correcto. No mencionó un detalle importante en su respuesta.

De los documentos bisect.bisect_left(a, x, lo=0, hi=len(a))

El módulo de bisección no requiere que la matriz de búsqueda se calcule previamente con anticipación. Simplemente puede presentar los puntos finales en bisect.bisect_leftlugar de usar los valores predeterminados de 0y len(a).

Aún más importante para mi uso, buscar un valor X tal que se minimice el error de una función determinada. Para hacer eso, necesitaba una forma de hacer que el algoritmo de bisect_left llamara a mi cálculo. Esto es realmente simple.

Solo proporcione un objeto que defina __getitem__comoa

¡Por ejemplo, podríamos usar el algoritmo de bisección para encontrar una raíz cuadrada con precisión arbitraria!

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
fuente
Esto no está limpio. Úselo scipy.optimizepara esto.
Neil G
4

Si solo quiere ver si está presente, intente convertir la lista 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

En mi máquina, "if n in l" tomó 37 segundos, mientras que "if n in d" tomó 0.4 segundos.

jrb
fuente
2
Esa no siempre es una buena opción por un par de razones: 1) los dictados / juegos ocupan más memoria. 2) si no tiene mucho en la lista, una búsqueda binaria puede ser más rápida. 3) convertir la lista a un dict es una operación O (n) mientras que una búsqueda binaria es O (log n).
Jason Baker
3
Como FYI, la sobrecarga "establecida" en python en comparación con las listas de python es muy, muy baja. Y son extremadamente rápidos para las búsquedas. Donde la búsqueda binaria realmente sobresale es para buscar rangos.
Gregg Lind
La conversión de la lista puede ser O (n), pero ordenar los datos en la lista, lo que tendría que hacer antes de realizar una búsqueda binaria, es peor. De dónde provienen los datos, probablemente pueda insertarlos en un diccionario a medida que avanza. Estoy de acuerdo en que la memoria puede ser un problema.
Mark Baker, el
4

Este es:

  • no recursivo (lo que lo hace más eficiente en memoria que la mayoría de los enfoques recursivos)
  • realmente trabajando
  • rápido ya que se ejecuta sin innecesarios if's y condiciones
  • basado en una afirmación matemática de que el piso de (bajo + alto) / 2 es siempre más pequeño que alto donde bajo es el límite inferior y alto es el límite superior.

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
fuente
¿Puedes compartir los casos de prueba?
Lifebalance
2

La solución de Dave Abrahams es buena. Aunque lo habría hecho minimalista:

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

Si bien no hay un algoritmo de búsqueda binaria explícito en Python, hay un módulo bisectdiseñado para encontrar el punto de inserción de un elemento en una lista ordenada mediante una búsqueda binaria. Esto puede ser "engañado" para que realice una búsqueda binaria. La mayor ventaja de esto es la misma ventaja que tiene la mayoría del código de la biblioteca: es de alto rendimiento, está bien probado y simplemente funciona (las búsquedas binarias en particular pueden ser bastante difíciles de implementar con éxito , especialmente si los casos límite no se consideran cuidadosamente).

Tipos basicos

Para tipos básicos como cadenas o entradas es bastante fácil: todo lo que necesita es el bisectmódulo y una lista ordenada:

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

También puede usar esto para encontrar duplicados:

...
>>> 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']

Obviamente, si lo desea, puede devolver el índice en lugar del valor de ese índice.

Objetos

Para los tipos u objetos personalizados, las cosas son un poco más complicadas: debe asegurarse de implementar métodos de comparación enriquecidos para obtener una bisección para comparar correctamente.

>>> 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']

Esto debería funcionar al menos en Python 2.7 -> 3.3

stephenfin
fuente
1

Al usar un dict no le gustaría duplicar el uso de su memoria a menos que los objetos que está almacenando sean realmente pequeños, ya que los valores son solo punteros a los objetos reales:

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

En ese ejemplo, 'foo' solo se almacena una vez. ¿Eso hace la diferencia para ti? ¿Y exactamente de cuántos artículos estamos hablando?

Kirk Strauser
fuente
Se trata de números y muchos de ellos :) Me gustaría usar una matriz casi tan grande como la memoria de la computadora. Sé que la base de mi problema podría estar mal, pero tenía curiosidad por la falta de un método de búsqueda binaria.
rslite
1
No puede tener un objeto clave lo suficientemente pequeño como para calificar como "realmente pequeño" aquí. Un objeto tendría un costo mínimo de 3 palabras (tipo, recuento, carga útil), mientras que una lista agrega 1 palabra, un conjunto agrega 1 palabra y un dict agrega 2 palabras. Los tres (lista / set / dict) preasignan espacio de alguna manera también, que es otro multiplicador, pero aún no es suficiente para importar.
Rhamphoryncus
1

Este código funciona con listas enteras de forma recursiva. Busca el escenario de caso más simple, que es: longitud de la lista menor que 2. Significa que la respuesta ya está allí y se realiza una prueba para verificar la respuesta correcta. De lo contrario, se establece un valor medio y se prueba que sea el correcto, si no se realiza la bisección llamando nuevamente a la función, pero estableciendo el valor medio como el límite superior o inferior, desplazándolo hacia la izquierda o la derecha

def binary_search (intList, intValue, lowValue, highValue):
    if (valor alto - valor bajo) <2:
        return intList [lowValue] == intValue o intList [highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue) / 2)
    if intList [middleValue] == intValue:
        volver verdadero
    if intList [middleValue]> intValue:
        return binary_search (intList, intValue, lowValue, middleValue - 1)
   return binary_search (intList, intValue, middleValue + 1, highValue)
rct
fuente
1

Consulte los ejemplos en 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
fuente
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

Supongo que esto es mucho mejor y efectivo. por favor corrigeme :) . Gracias

iraycd
fuente
0
  • s es una lista
  • binary(s, 0, len(s) - 1, find) es la llamada inicial
  • La función devuelve un índice del elemento consultado. Si no hay tal artículo, regresa -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
fuente
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
usuario3412550
fuente
0

Búsqueda binaria :

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

// Para llamar a la función anterior use:

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
fuente
0

Necesitaba búsqueda binaria en python y genérica para los modelos Django. En los modelos Django, un modelo puede tener una clave foránea para otro modelo y quería realizar alguna búsqueda en los objetos de los modelos recuperados. Escribí la siguiente función, puedes usar esto.

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
fuente
0

Muchas buenas soluciones anteriores, pero no he visto un uso simple (KISS lo mantiene simple (porque soy) estúpido de la función bisecta / genérica incorporada de Python para hacer una búsqueda binaria. Con un poco de código alrededor de la función bisecta, Creo que tengo un ejemplo a continuación donde probé todos los casos para una pequeña serie de nombres de cadenas. Algunas de las soluciones anteriores aluden / dicen esto, pero espero que el código simple a continuación ayude a cualquiera a confundirse como yo.

Python bisect se usa para indicar dónde insertar un nuevo valor / elemento de búsqueda en una lista ordenada. El siguiente código que usa bisect_left que devolverá el índice del hit si se encuentra el elemento de búsqueda en la lista / matriz (tenga en cuenta que bisect y bisect_right devolverán el índice del elemento después del hit o match como punto de inserción) Si no se encuentra , bisect_left devolverá un índice al siguiente elemento de la lista ordenada que no == el valor de búsqueda. El único otro caso es donde el elemento de búsqueda iría al final de la lista donde el índice devuelto estaría más allá del final de la lista / matriz, y que en el código debajo de la salida temprana de Python con "y" maneja la lógica. (primera condición False Python no verifica condiciones posteriores)

#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
Beto
fuente