Búsqueda binaria (bisección) en Python

Question

¿Existe una función de biblioteca que realice una búsqueda binaria en una lista / tupla y devuelva 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í regresan 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_left y 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 consulta 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.

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

¿Por qué no busca el código para bisect_left / right y lo adapta a su propósito?

como este:

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

Answer 3

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)
• Insertar / eliminar O (n) (puede ser un caso promedio O (1) u O (log n), según 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 () genera muy poca sobrecarga adicional en python .

Answer 4

Podría valer la pena mencionar que los documentos de bisect ahora proporcionan ejemplos de búsqueda: http://docs.python.org/library/bisect.html#searching -las listas de clasificación

(Elevar ValueError en lugar de devolver -1 o Ninguno es más pythónico. & # 8211; list.index () lo hace, por ejemplo. Pero, por supuesto, puede adaptar los ejemplos a sus necesidades.)

Answer 5

Más simple es usar bisect y verifique una posición 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

Answer 6

Esto es correcto del manual:

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

8.5.1. Buscando 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

Answer 7

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.

Del docs 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 precompute de antemano. Simplemente puede presentar los puntos finales a bisect.bisect_left en lugar de utilizar los valores predeterminados de 0 y 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.

Simplemente proporcione un objeto que defina __getitem__ como a

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

Answer 8

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, " si n en l " tomó 37 segundos, mientras que "si n en d" tomó 0.4 segundos.

Answer 9

Este es:

• no recursivo (lo que lo hace más eficiente en memoria que la mayoría de los enfoques recursivos)
• en realidad trabajando
• rápido, ya que se ejecuta sin ningún if y condiciones innecesarios
• basado en una afirmación matemática de que el piso de (bajo + alto) / 2 siempre es más pequeño que alto donde bajo es el límite inferior y alto es el límite superior.
• probado: 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

Answer 10

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

Answer 11

Si bien no hay un algoritmo de búsqueda binaria explícito en Python, hay un módulo, bisect , diseñ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 realizar una búsqueda binaria. La mayor ventaja de esto es la misma ventaja que tiene la mayoría de los códigos de biblioteca: es de alto rendimiento, está bien probado y simplemente funciona (las búsquedas binarias en particular pueden ser bastante difícil de implementar con éxito , especialmente si los casos de borde no se consideran cuidadosamente).

Tipos básicos

Para tipos básicos como Strings o ints es bastante fácil, todo lo que necesita es el módulo bisect 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 puedes 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 tipos u objetos personalizados, las cosas son un poco más complicadas: debes asegurarte de implementar métodos de comparación enriquecidos para que bisect se compare 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

Answer 12

Al usar un dict no le gustaría duplicar el uso de la memoria a menos que los objetos que está almacenando sean realmente pequeños, ya que los valores solo son 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 una diferencia para ti? ¿Y exactamente de cuántos artículos estamos hablando?

Answer 13

Este código funciona con listas de enteros de forma recursiva. Busca el escenario de caso más simple, que es: la longitud de la lista es 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 hacia la derecha

< p>

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) < 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)

Answer 14

Vea 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

Answer 15

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

Answer 16

• s es una lista.
• binario (s, 0, len (s) - 1, find) es la llamada inicial.

• La función devuelve un índice del elemento consultado. Si no hay tal elemento, devuelve -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)
  

Answer 17

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

Answer 18

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 al uso de la función anterior:

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

Answer 19

Necesitaba búsqueda binaria en python y genérica para los modelos de Django. En los modelos de Django, un modelo puede tener una clave externa para otro modelo y quería realizar una búsqueda en los objetos de 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

Answer 20

Muchas de las buenas soluciones anteriores, pero no he visto una simple (KISS es simple (porque soy) uso estúpido de la función bisecta / genérica Python integrada para hacer una búsqueda binaria. Con un poco de código en torno a función bisect, creo que tengo un ejemplo a continuación donde he probado todos los casos para una pequeña cadena de nombres. Algunas de las soluciones anteriores aluden a / dicen esto, pero espero que el código simple a continuación ayude a cualquier persona confundida como yo.

Python bisect se utiliza 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 en 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 las 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