programas - metodo de la secante python

Búsqueda binaria(bisección) en Python

Question

¿Existe una función de biblioteca que realiza búsqueda binaria en una lista / tupla y devuelve la posición del artículo si se encuentra y ''False'' (-1, None, etc.) si no es así?

Encontré las funciones bisect_left / right en el módulo bisect , pero aún 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 artículo 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 parece engorroso (y también necesito hacer límites verificando si el número puede ser mayor que el número más grande en mi lista) . Si hay un método más agradable, me gustaría saber al respecto.

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 según su índice. Y también quiero poder encontrar el índice de un valor particular o None si el valor no está en la lista.

Usar un diccionario para esto sería la forma más rápida, pero duplicaría (aproximadamente) 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

¿Por qué no mira el código de bisect_left / right y lo adapta 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

Answer 2

Echa un vistazo a 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 3

Este es:

• no recursivo (lo que lo hace más eficiente con la memoria que la mayoría de los enfoques recursivos)
• realmente trabajando
• rápido, ya que se ejecuta sin ningún tipo de condiciones y condiciones innecesarias
• basado en una aserció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 4

Esto es correcto desde el manual:

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

8.5.1. Búsqueda de listas ordenadas

Las funciones bisect () anteriores son útiles para encontrar puntos de inserción, pero pueden ser difíciles o incómodas 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 5

Esto es un poco fuera de tema (ya que la respuesta de Moe parece completa a la pregunta del OP), pero valdría la pena analizar la complejidad de todo el procedimiento de principio a fin. Si está almacenando cosas en una lista ordenada (que es donde ayudaría una búsqueda binaria), y luego solo verifica su 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 no ordenados, O (n), si está ordenada)
• O (log n) búsquedas (esta es la parte de búsqueda binaria)
• O (n) insertar / borrar (podría ser el caso promedio de O (1) o O (log n), dependiendo de su patrón)

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

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

Lo que realmente obtiene una lista ordenada es "siguiente", "anterior" y "rangos" (incluidos los intervalos de inserción o eliminación), que son O (1) o O (| rango |), dado un índice de inicio. Si no está utilizando ese tipo de operaciones a menudo, entonces almacenarlas como conjuntos y ordenarlas para mostrarlas puede ser una mejor oferta en general. set() incurre en muy poca carga adicional en python.

Answer 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 docs bisect.bisect_left(a, x, lo=0, hi=len(a))

El módulo de bisección no requiere que el conjunto de búsqueda sea precalculado antes de tiempo. Puede presentar los puntos finales en bisect.bisect_left lugar de usar los valores predeterminados de 0 y len(a) .

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

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

La solución de Dave Abrahams es buena. Aunque lo hubiera hecho, lo habría hecho de forma 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 8

Lo más simple es usar bisección y verificar 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 9

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

Python bisect se usa para indicar dónde insertar un nuevo elemento de valor / búsqueda en una lista ordenada. El siguiente código utiliza bisect_left que devolverá el índice del hit si se encuentra el elemento de búsqueda en la lista / matriz (Note bisect y bisect_right devolverá 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

Answer 10

Necesitaba una 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 11

Si bien no existe un algoritmo de búsqueda binario explícito en Python, existe 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 del código de la biblioteca: es de alto rendimiento, bien probado y simplemente funciona (las búsquedas binarias en particular pueden ser bastante difíciles de implementar con éxito , especialmente si los casos extremos no se consideran cuidadosamente).

Tipos basicos

Para tipos básicos como Strings o ints, es bastante fácil; todo lo que necesitas 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, puede devolver el índice en lugar del valor en ese índice si lo desea.

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 comparación correcta.

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

Si solo quieres ver si está presente, intenta 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" tardó 37 segundos, mientras que "si n en d" tomó 0,4 segundos.

Answer 13

Usar un dict no quiere duplicar el uso de tu memoria a menos que los objetos que estás almacenando sean muy 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 14

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

(Aumentar ValueError en lugar de devolver -1 o None es más pythonic, por ejemplo, list.index (). Pero, por supuesto, puede adaptar los ejemplos a sus necesidades).

Answer 15

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

Answer 16

Este código funciona con listas de enteros de forma recursiva. Busca el escenario más simple, que es: longitud de lista menor que 2. Significa que la respuesta ya está allí y se realiza una prueba para verificar la respuesta correcta. Si no, se establece y se prueba que el valor medio es el correcto, si no se realiza la bisección llamando de nuevo 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

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)

Answer 17

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 18

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

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 20

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

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