Ricerca binaria (bisection) in Python

Question

Esiste una funzione di libreria che esegue la ricerca binaria in un elenco / tupla e restituisce la posizione dell'elemento se trovato e 'Falso' (-1, Nessuno, ecc.) In caso contrario?

Ho trovato le funzioni bisect_left / right nel modulo bisect , ma continuano a tornare una posizione anche se l'elemento non è nell'elenco. Va benissimo per l'uso previsto, ma voglio solo sapere se un elemento è nell'elenco o no (non voglio inserire nulla).

Ho pensato di usare bisect_left e quindi verificare se l'oggetto in quella posizione è uguale a quello che sto cercando, ma sembra ingombrante (e devo anche fare dei limiti controllando se il numero può essere più grande del numero più grande nella mia lista). Se esiste un metodo migliore, mi piacerebbe saperlo.

Modifica Per chiarire di cosa ho bisogno: sono consapevole che un dizionario sarebbe molto adatto a questo, ma sto cercando di mantenere il consumo di memoria il più basso possibile. Il mio uso previsto sarebbe una sorta di tabella di ricerca a doppio senso. Nella tabella ho un elenco di valori e devo poter accedere ai valori in base al loro indice. E voglio anche essere in grado di trovare l'indice di un determinato valore o Nessuno se il valore non è nell'elenco.

L'uso di un dizionario per questo sarebbe il modo più veloce, ma raddoppierebbe (approssimativamente) i requisiti di memoria.

Stavo ponendo questa domanda pensando che avrei potuto trascurare qualcosa nelle librerie di Python. Sembra che dovrò scrivere il mio codice, come suggerì 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

Perché non guardare il codice per bisect_left / right e adattarlo al tuo scopo.

in questo modo:

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

Questo è un po 'fuori tema (poiché la risposta di Moe sembra completa alla domanda del PO), ma potrebbe valere la pena esaminare la complessità dell'intera procedura da un capo all'altro. Se stai memorizzando qualcosa in un elenco ordinato (che è dove una ricerca binaria potrebbe aiutare), e poi stai solo verificando l'esistenza, stai affrontando (nel peggiore dei casi, se non specificato):

Elenchi ordinati

• O (n log n) per creare inizialmente l'elenco (se si tratta di dati non ordinati. O (n), se è ordinato)
• O (log n) ricerche (questa è la parte di ricerca binaria)
• O (n) inserisci / elimina (potrebbe essere O (1) o O (log n) caso medio, a seconda del modello)

Considerando che con un set () , stai affrontando

• O (n) per creare
• Ricerca O (1)
• O (1) inserisci / elimina

La cosa che ti dà veramente un elenco ordinato è "prossimo", "precedente", "e" intervalli ". (incluso l'inserimento o l'eliminazione di intervalli), che sono O (1) o O (| intervallo |), dato un indice iniziale. Se non si utilizzano spesso questo tipo di operazioni, la memorizzazione come set e l'ordinamento per la visualizzazione potrebbero essere nel complesso un affare migliore. set () comporta pochissime spese generali aggiuntive in python .

Answer 4

Potrebbe valere la pena ricordare che i documenti bisect ora forniscono esempi di ricerca: http://docs.python.org/library/bisect.html#searching -sorted-liste

(Aumentare ValueError invece di restituire -1 o None è più pythonic - list.index () lo fa, per esempio. Ma ovviamente puoi adattare gli esempi alle tue esigenze.)

Answer 5

Il più semplice è usare bisect e ricontrollare una posizione per vedere se l'oggetto è c'è:

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

Questo è direttamente dal manuale:

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

8.5.1. Ricerca negli elenchi ordinati

Le suddette funzioni bisect () sono utili per trovare punti di inserimento, ma possono essere complicate o scomode da usare per attività di ricerca comuni. Le seguenti cinque funzioni mostrano come trasformarle nelle ricerche standard per elenchi ordinati:

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

Quindi con la leggera modifica il tuo codice dovrebbe essere:

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

Sono d'accordo che @ La risposta di DaveAbrahams utilizzando il modulo bisect è l'approccio corretto. Non ha menzionato un dettaglio importante nella sua risposta.

Dalla docs .bisect_left (a, x, lo = 0, hi = len (a))

Il modulo bisection non richiede che l'array di ricerca sia precompilato in anticipo. Puoi semplicemente presentare gli endpoint al bisect.bisect_left invece che usando i valori predefiniti di 0 e len (a) .

Ancora più importante per il mio uso, cercare un valore X tale che l'errore di una determinata funzione sia ridotto al minimo. Per fare ciò, avevo bisogno di un modo per far sì che l'algoritmo di bisect_left chiamasse il mio calcolo. Questo è davvero semplice.

Fornisci semplicemente un oggetto che definisce __getitem__ come a

Ad esempio, potremmo usare l'algoritmo bisect per trovare una radice quadrata con precisione 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

Se vuoi solo vedere se è presente, prova a trasformare l'elenco in 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

Sulla mia macchina, " if n in l " ha impiegato 37 secondi, mentre "se n in d" ha impiegato 0,4 secondi.

Answer 9

Questo è:

• non ricorsivo (che lo rende più efficiente in termini di memoria rispetto alla maggior parte degli approcci ricorsivi)
• attualmente funzionante
• veloce poiché funziona senza alcun if e condizioni
inutili
• basato su un'asserzione matematica che il piano di (basso + alto) / 2 è sempre più piccolo di alto dove basso è il limite inferiore e alto è il limite superiore.
• testato: 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 soluzione di Dave Abrahams è buona. Anche se l'avrei fatto 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

Anche se non esiste un algoritmo di ricerca binaria esplicito in Python, esiste un modulo - bisect - progettato per trovare il punto di inserimento di un elemento in un elenco ordinato usando una ricerca binaria. Questo può essere "ingannato" nell'esecuzione di una ricerca binaria. Il più grande vantaggio di questo è lo stesso vantaggio della maggior parte del codice della libreria: è ad alte prestazioni, ben testato e funziona bene (in particolare le ricerche binarie possono essere abbastanza difficile da implementare con successo - in particolare se i casi limite non sono attentamente considerati).

Tipi di base

Per tipi di base come stringhe o ints è abbastanza facile - tutto ciò che serve è il modulo bisect e un elenco ordinato:

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

Puoi anche usarlo per trovare duplicati:

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

Ovviamente potresti semplicemente restituire l'indice anziché il valore in quell'indice, se lo desideri.

Oggetti

Per i tipi o gli oggetti personalizzati, le cose sono un po 'più complicate: devi assicurarti di implementare metodi di confronto avanzati per ottenere il bisect per confrontare correttamente.

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

Questo dovrebbe funzionare almeno in Python 2.7 - > 3.3

Answer 12

L'uso di un dict non vorrebbe raddoppiare l'utilizzo della memoria a meno che gli oggetti che stai memorizzando non siano davvero minuscoli, poiché i valori sono solo puntatori agli oggetti reali:

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

In questo esempio, "pippo" viene memorizzato una sola volta. Questo fa la differenza per te? Ed esattamente di quanti articoli stiamo parlando?

Answer 13

Questo codice funziona con elenchi di numeri interi in modo ricorsivo. Cerca lo scenario del caso più semplice, ovvero: lunghezza elenco inferiore a 2. Indica che la risposta è già presente e viene eseguito un test per verificare la risposta corretta. In caso contrario, un valore medio viene impostato e testato per essere corretto, in caso contrario viene eseguita richiamando la funzione, ma impostando il valore medio come limite superiore o inferiore, spostandolo a sinistra o a destra

< 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

Guarda gli esempi su 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

Immagino che sia molto meglio ed efficace. per favore correggimi :). Grazie

Answer 16

• s è un elenco.
• binary (s, 0, len (s) - 1, find) è la chiamata iniziale.

• La funzione restituisce un indice dell'elemento interrogato. Se non esiste tale elemento, viene restituito -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

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

// Per chiamare la funzione precedente utilizzare:

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

Avevo bisogno di una ricerca binaria in Python e generica per i modelli Django. Nei modelli Django, un modello può avere una chiave esterna per un altro modello e volevo eseguire qualche ricerca sugli oggetti dei modelli recuperati. Ho scritto la seguente funzione che puoi usare.

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

Molte buone soluzioni di cui sopra, ma non ho visto un semplice (KISS Keep it Simple (perché sono) stupido uso della funzione bisect generica / generica di Python per fare una ricerca binaria. Con un po 'di codice attorno al bisect, credo di avere un esempio di seguito in cui ho testato tutti i casi per una piccola serie di nomi di stringhe. Alcune delle soluzioni di cui sopra alludono a / dicono questo, ma si spera che il semplice codice qui sotto possa aiutare chiunque sia confuso come me.

Python bisect viene utilizzato per indicare dove inserire un nuovo valore / elemento di ricerca in un elenco ordinato. Il codice seguente che utilizza bisect_left che restituirà l'indice dell'hit se viene trovato l'elemento di ricerca nell'elenco / array (Nota bisect e bisect_right restituiranno l'indice dell'elemento dopo l'hit o la corrispondenza come punto di inserimento) Se non trovato , bisect_left restituirà un indice all'elemento successivo nell'elenco ordinato che non sarà == il valore di ricerca. L'unico altro caso è dove l'elemento di ricerca andrebbe alla fine dell'elenco in cui l'indice restituito sarebbe oltre la fine dell'elenco / matrice e che nel codice sotto l'uscita anticipata di Python con " e " maniglie logiche. (prima condizione False Python non controlla le condizioni successive)

#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