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

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

¿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

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.

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

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

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

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)

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.

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

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

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

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?

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)

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

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

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

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

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

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

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