Pesquisa binária (bissecção) em Python

176

Existe uma função de biblioteca que realiza pesquisa binária em uma lista / tupla e retorna a posição do item, se encontrado, e 'Falso' (-1, Nenhum, etc.), se não?

Encontrei as funções bisect_left / right no módulo bisect , mas elas ainda retornam uma posição mesmo que o item não esteja na lista. Isso é perfeitamente adequado para o uso pretendido, mas eu só quero saber se um item está na lista ou não (não quero inserir nada).

Pensei em usar bisect_lefte depois verificar se o item nessa posição é igual ao que estou procurando, mas isso parece complicado (e também preciso verificar os limites se o número pode ser maior que o maior número da minha lista). Se houver um método melhor, eu gostaria de saber sobre isso.

Editar Para esclarecer o que eu preciso disso: estou ciente de que um dicionário seria muito adequado para isso, mas estou tentando manter o consumo de memória o mais baixo possível. Meu uso pretendido seria uma espécie de tabela de consulta de duas vias. Eu tenho na tabela uma lista de valores e preciso poder acessar os valores com base em seu índice. E também quero encontrar o índice de um valor específico ou Nenhum se o valor não estiver na lista.

Usar um dicionário para isso seria a maneira mais rápida, mas dobraria (aproximadamente) os requisitos de memória.

Eu estava fazendo essa pergunta pensando que poderia ter esquecido algo nas bibliotecas Python. Parece que vou ter que escrever meu próprio código, como sugeriu Moe.

rslite
fonte
1
O que você está tentando realizar? Se os valores forem únicos, considere usar um conjunto e "se o valor no conjunto: alguma coisa".
21410 Kirk Strauser
Pelo que vale, "-1" é considerado verdadeiro; "0" seria falso.
Glyph
3
Eu mencionei -1 porque uma função que retorna o índice do item pesquisado na matriz já pode retornar 0, portanto -1 será retornado se o item não for encontrado (semelhante à pesquisa de substring).
Rslite 18/10/08
3
Se você usa numpy, np.searchsortedé útil. docs.scipy.org/doc/numpy/reference/generated/…
Roman Shapovalov

Respostas:

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
fonte
10
@ vulcano O mesmo acontece com a pesquisa geral.
precisa saber é o seguinte
4
@TomSwirly não tão simples como o seu, mas correta e ainda uma melhoria:if hi is None: hi = len(a)
Mark Ransom
E quanto à ordem decrescente?
Parikshit Chalke
2
Você pode adicionar alguma explicação fora do código? Os padrões aqui foram alterados.
SS Anne
54

Por que não olhar para o código bisect_left / right e adaptá-lo para se adequar ao seu objetivo.

como isso:

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
fonte
29
Marquei isso com +1, mas agora cheguei à conclusão de que isso não é uma coisa boa. Se essa resposta for seguida, causará muita duplicação de código e, como todos sabemos, é muito simples pesquisar a pesquisa binária.
abyx 30/10/09
1
não deveria estar hi = mid - 1no elif?
Paweł Prażak
7
@ Paweł: são duas variantes equivalentes, dependendo se o limite superior é inclusivo ou exclusivo. você pode mudar hi = midpara hi = mid-1e hi = len(a)de hi = len(a)-1e while lo < hi:para while lo <= hi, e seria equivalente correta
user102008
2
por que não fazer algo como: def binary_search (a, x, lo = 0, oi = Nenhum): i = bisect (a, x, lo, oi) retorna i se a [i] == x else -1 desculpe pelo formatação - não sei como fazer isso corretamente no comentário arrea
Vitali
1
Você deve usar bisect.bisect_left()em vez disso.
Alastair 07/11
37

Isso é um pouco fora de tópico (já que a resposta de Moe parece completa para a pergunta do OP), mas pode valer a pena examinar a complexidade de todo o procedimento de ponta a ponta. Se você estiver armazenando algo em listas classificadas (que é onde uma pesquisa binária ajudaria) e depois apenas verificando a existência, está ocorrendo (na pior das hipóteses, a menos que seja especificado):

Listas ordenadas

  • O (n log n) para criar inicialmente a lista (se houver dados não classificados. O (n), se estiver classificado)
  • O (log n) pesquisas (esta é a parte de pesquisa binária)
  • O (n) inserção / exclusão (pode ser o caso médio de O (1) ou O (log n), dependendo do seu padrão)

Considerando que com a set(), você está incorrendo

  • O (n) para criar
  • O (1) pesquisa
  • O (1) inserir / excluir

A única coisa que uma lista classificada realmente mostra é "próximo", "anterior" e "intervalos" (incluindo a inserção ou exclusão de intervalos), que são O (1) ou O (| intervalo |), com um índice inicial. Se você não estiver usando esse tipo de operação com frequência, armazenar como conjuntos e classificar para exibição pode ser um negócio melhor em geral. set()incorre muito pouco em sobrecarga adicional em python.

Gregg Lind
fonte
7
Há uma outra coisa que uma lista classificada leva você. O (n) ordenou a travessia. Com um conjunto que é O (n log n) e você acaba copiando as referências aos dados em uma lista.
Onipóreo 30/03/10
1
É verdade! Obrigado por expandir o que eu quis dizer com pesquisa por intervalo. Fwiw, um percurso completo é a mesma consulta intervalo entre um mínimo e máximo, que é O (k), onde k = n :)
Gregg Lind
14

Vale a pena mencionar que os documentos bisectados agora fornecem exemplos de pesquisa: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Aumentar ValueError em vez de retornar -1 ou None é mais pythonic - list.index () faz, por exemplo. Mas é claro que você pode adaptar os exemplos às suas necessidades.)

Petr Viktorin
fonte
11

O mais simples é usar o bisset e verificar uma posição novamente para ver se o item está lá:

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
fonte
2
Bom, mas o código barfs se você não passar o valor 'oi'. Eu escreveria assim: "def binary_search (a, x, lo = 0, hi = None): da importação de bisect bisect i = bisect (a, x, lo, oi ou len (a)) return (i- 1 se a [i-1] == x else -1) "e teste-o assim:" para i no intervalo (1, 20): a = lista (intervalo (i)) para aa no a: j = binary_search (a, aa) se j = aa: imprimir i, aa, j"
hughdbrown
8

Isso está correto no manual:

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

8.5.1 Pesquisando Listas Classificadas

As funções bisect () acima são úteis para encontrar pontos de inserção, mas podem ser difíceis ou difíceis de usar para tarefas comuns de pesquisa. As cinco funções a seguir mostram como transformá-las nas pesquisas padrão para listas classificadas:

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

Portanto, com a pequena modificação, seu código deve 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
fonte
6

Concordo que a resposta de @ DaveAbrahams usando o módulo bisect é a abordagem correta. Ele não mencionou um detalhe importante em sua resposta.

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

O módulo de bissecção não exige que a matriz de pesquisa seja pré-computada com antecedência. Você pode apenas apresentar os pontos de extremidade ao bisect.bisect_leftinvés dele, usando os padrões de 0elen(a) .

Ainda mais importante para o meu uso, procurando um valor X tal que o erro de uma determinada função seja minimizado. Para fazer isso, eu precisava de uma maneira de o algoritmo do bisect_left chamar minha computação. Isto é realmente simples.

Basta fornecer um objeto que define __getitem__ comoa

Por exemplo, poderíamos usar o algoritmo bisect para encontrar uma raiz quadrada com precisão arbitrária!

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
fonte
Isto não está limpo. Use scipy.optimizepara isso.
Neil G
4

Se você quiser apenas ver se está presente, tente transformar a lista em um ditado:

# 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

Na minha máquina, "se n em l" levou 37 segundos, enquanto "se n em d" levou 0,4 segundos.

jrb
fonte
2
Isso nem sempre é uma boa opção por algumas razões: 1) dict / sets consomem mais memória. 2) se ele não tiver muito na lista, uma pesquisa binária pode ser mais rápida. 3) converter a lista em um ditado é uma operação O (n) enquanto uma pesquisa binária é O (log n).
21380 Jason Baker
3
Como FYI, a sobrecarga "set" no python em comparação com as listas python é muito muito baixa. E eles são extremamente rápidos para pesquisas. Onde a pesquisa binária realmente se destaca é procurar os intervalos.
Gregg Lind
A conversão da lista pode ser O (n), mas a classificação dos dados na lista, o que você precisaria fazer antes da pesquisa binária, é pior. De onde vêm os dados, você provavelmente pode inseri-los em um dicionário à medida que avança. Concordo que a memória pode ser um problema.
Mark Baker
4

Esta está:

  • não recursivo (o que torna mais eficiente em termos de memória a que a maioria das abordagens recursivas)
  • na realidade trabalhando
  • rápido, pois é executado sem necessidade desnecessária if e condições
  • com base em uma afirmação matemática de que o piso de (baixo + alto) / 2 é sempre menor que alto, onde baixo é o limite inferior e alto é o limite 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
fonte
Você pode compartilhar os casos de teste?
lifebalance
2

A solução de Dave Abrahams é boa. Embora eu tivesse feito isso 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
fonte
2

Embora não exista um algoritmo explícito de pesquisa binária no Python, existe um módulo - bisect- projetado para encontrar o ponto de inserção de um elemento em uma lista classificada usando uma pesquisa binária. Isso pode ser "enganado" na realização de uma pesquisa binária. A maior vantagem disso é a mesma vantagem que o código de biblioteca tem - é de alto desempenho, bem testado e simplesmente funciona (pesquisas binárias em particular podem ser bastante difíceis de implementar com sucesso - principalmente se os casos extremos não forem considerados com cuidado).

Tipos básicos

Para tipos básicos como Strings ou ints, é muito fácil - tudo o que você precisa é do bisectmódulo e de uma lista classificada:

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

Você também pode usar isso para encontrar duplicatas:

...
>>> 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, você pode simplesmente retornar o índice em vez do valor nesse índice, se desejar.

Objetos

Para tipos ou objetos personalizados, as coisas são um pouco mais complicadas: você precisa implementar métodos de comparação sofisticados para que a bissecção seja comparada corretamente.

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

Isso deve funcionar em pelo menos Python 2.7 -> 3.3

stephenfin
fonte
1

Usar um ditado não gostaria de duplicar o uso de memória, a menos que os objetos que você esteja armazenando sejam realmente minúsculos, pois os valores são apenas indicadores dos objetos reais:

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

Nesse exemplo, 'foo' é armazenado apenas uma vez. Isso faz diferença para você? E exatamente de quantos itens estamos falando?

Kirk Strauser
fonte
É sobre números e muitos deles :) Gostaria de usar uma matriz quase tão grande quanto a memória do computador. Sei que a base do meu problema pode estar errada, mas fiquei curioso com a falta de um método de pesquisa binária.
rslite
1
Você não pode ter um objeto-chave pequeno o suficiente para se qualificar como "realmente pequeno" aqui. Um objeto teria um custo mínimo de 3 palavras (tipo, refcount, carga), enquanto uma lista adiciona 1 palavra, um conjunto adiciona 1 palavra e um ditado adiciona 2 palavras. Todos os três (listar / definir / ditar) também alocam espaço de alguma maneira, o que é outro multiplicador, mas ainda não é suficiente para importar.
Rhamphoryncus
1

Esse código funciona com listas inteiras de maneira recursiva. Procura o cenário de caso mais simples, que é: comprimento da lista menor que 2. Isso significa que a resposta já está lá e um teste é executado para verificar a resposta correta. Caso contrário, um valor do meio é definido e testado para ser o correto, caso contrário a bissecção é executada chamando novamente a função, mas definindo o valor do meio como o limite superior ou inferior, deslocando-o para a esquerda ou direita

def binary_search (intList, intValue, lowValue, highValue):
    if (valor alto - valor baixo) <2:
        retornar intList [lowValue] == intValue ou intList [highValue] == intValue
    middleValue = valor baixo + ((valor alto - valor baixo) / 2)
    if intList [middleValue] == intValue:
        retornar True
    if intList [middleValue]> intValue:
        retornar binary_search (intList, intValue, lowValue, middleValue - 1)
   retornar binary_search (intList, intValue, middleValue + 1, highValue)
rct
fonte
1

Confira os exemplos na 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
fonte
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

Eu acho que isso é muito melhor e eficaz. Por favor me corrija :) . Obrigado

iraycd
fonte
0
  • s é uma lista.
  • binary(s, 0, len(s) - 1, find) é a chamada inicial.
  • A função retorna um índice do item consultado. Se não houver esse item, ele retornará -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
fonte
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
user3412550
fonte
0

Pesquisa binária:

// 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 chamar a função acima, 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
fonte
0

Eu precisava de pesquisa binária em python e genérica para modelos do Django. Nos modelos do Django, um modelo pode ter chave estrangeira para outro modelo e eu queria realizar alguma pesquisa nos objetos de modelos recuperados. Eu escrevi a seguinte função, você pode usar isso.

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

Muitas boas soluções acima, mas eu não vi um uso estúpido (o KISS simplifica (porque eu sou)) da função bisect incorporada / genérica do Python para fazer uma pesquisa binária.Com um pouco de código em torno da função bisect, Eu acho que tenho um exemplo abaixo, onde testei todos os casos para uma pequena matriz de nomes de caracteres.Algumas das soluções acima mencionam / dizem isso, mas espero que o código simples abaixo ajude qualquer pessoa confusa como eu.

O Python bisect é usado para indicar onde inserir um novo valor / item de pesquisa em uma lista classificada. O código abaixo que usa bisect_left que retornará o índice da ocorrência se o item de pesquisa na lista / matriz for encontrado (observe bisect e bisect_right retornará o índice do elemento após a ocorrência ou correspondência como ponto de inserção) Se não encontrado , bisect_left retornará um índice para o próximo item na lista classificada que não será == o valor da pesquisa. O único outro caso é onde o item de pesquisa iria no final da lista, onde o índice retornado estaria além do final da lista / matriz e que, no código abaixo da saída antecipada do Python, com identificadores lógicos "e". (primeira condição, o False Python não verifica as condições subseqüentes)

#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
Prumo
fonte