Trabalhar com listas classificadas às vezes pode ser um pouco complicado. Você precisa manter a ordem da lista após cada inserção e pesquisar com eficiência os elementos dentro dela. A pesquisa binária é um algoritmo poderoso para pesquisar em uma lista ordenada. Embora implementá-lo do zero não seja muito difícil, pode ser demorado. Felizmente, Python oferece o módulo bisect, que facilita muito o manuseio de listas classificadas.

O que é pesquisa binária?

A pesquisa binária é um algoritmo que encontra a posição de um valor alvo dentro de uma matriz classificada. Imagine que você está procurando um nome em uma lista telefônica. Em vez de começar na primeira página, você provavelmente começará no meio do livro e decidirá se deseja continuar a pesquisa na primeira ou na segunda metade, dependendo se o nome é alfabeticamente maior ou menor que o do meio. A pesquisa binária funciona de maneira semelhante: começa com dois ponteiros, um no início e outro no final da lista. O elemento do meio é então calculado e comparado ao alvo.

O Módulo bisect: Simplificando Operações de Lista Classificada

Embora a pesquisa binária seja eficaz, escrever a implementação sempre pode ser entediante. Mas e se você pudesse realizar as mesmas operações com apenas uma linha de código? É aí que entra o módulo bisect do Python. Parte da biblioteca padrão do Python, bisect ajuda a manter uma lista ordenada sem a necessidade de classificá-la após cada inserção. Isso é feito usando um algoritmo de bissecção simples.

O módulo bisect fornece duas funções principais: bisect e insort. A função bisect encontra o índice onde um elemento deve ser inserido para manter a lista ordenada, enquanto insort insere o elemento na lista enquanto mantém sua ordem de classificação.

Usando o módulo bisect: um exemplo prático

Vamos começar importando o módulo:

import bisect

Exemplo 1: Inserindo um Número em uma Lista Classificada

Suponha que temos uma lista ordenada de números:

data = [1, 3, 5, 6, 8]

Para inserir um novo número mantendo a lista ordenada, basta usar:

bisect.insort(data, 7)

depois de executar este código, os dados ficarão assim:

[1, 3, 5, 6, 7, 8]

Exemplo 2: Encontrando o Ponto de Inserção

E se você quiser apenas descobrir onde um número seria inserido sem realmente inseri-lo? Você pode usar as funções bisect_left ou bisect_right:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Isso nos diz que o número 4 deve ser inserido no índice 2 para manter a lista ordenada.

Exemplo 3: Manutenção da ordem classificada em uma lista dinâmica

Digamos que você esteja gerenciando uma lista que cresce dinamicamente e precise inserir elementos enquanto garante que ela permaneça ordenada:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Isso gerará a lista em cada etapa à medida que os elementos são inseridos:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Exemplo 4: Usando bisect com objetos personalizados

Suponha que você tenha uma lista de objetos personalizados, como tuplas, e queira inseri-los com base em um critério específico:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Ou você pode querer inserir com base no segundo elemento de cada tupla:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect em ação: em busca de palavras

O módulo bisect não está limitado a números; também pode ser útil para pesquisar listas de strings, tuplas, caracteres etc.
Por exemplo, para encontrar uma palavra em uma lista ordenada:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Ou para encontrar a primeira palavra em um grupo de palavras com um prefixo específico:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

No entanto, lembre-se de que bisect_left retorna o índice onde o alvo deve ser inserido, e não se o alvo existe na lista.

Variantes de bisect e insort

O módulo também inclui variantes do lado direito: bisect_right e insort_right. Essas funções retornam o índice mais à direita no qual inserir um elemento se ele já estiver na lista. Por exemplo, bisect_right retornará o índice do primeiro elemento maior que o alvo se o alvo estiver na lista, enquanto insort_right insere o elemento nessa posição.

dividir sob o capô

O poder do módulo bisect reside em sua implementação eficiente do algoritmo de pesquisa binária. Quando você chama bisect.bisect_left, por exemplo, a função essencialmente executa uma pesquisa binária na lista para determinar o ponto de inserção correto para o novo elemento.

Veja como funciona nos bastidores:

1. Inicialização: A função começa com dois ponteiros, lo e hi, que representam os limites inferior e superior do intervalo de pesquisa dentro da lista. Inicialmente, lo é colocado no início da lista (índice 0) e hi é colocado no final da lista (índice igual ao comprimento da lista). Mas você também pode especificar valores lo e hi personalizados para pesquisar em um intervalo específico da lista.

2. Bissecção: Dentro de um loop, a função calcula o ponto médio (mid) entre lo e hi. Em seguida, ele compara o valor intermediário com o valor alvo que você deseja inserir.

3. Comparação:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. Terminação: Este processo continua, reduzindo pela metade o intervalo de pesquisa a cada vez, até que lo seja igual a hi. Neste ponto, lo (ou hi) representa o índice correto onde o alvo deve ser inserido para manter a ordem de classificação da lista.

2. Inserção: para a função insort, uma vez encontrado o índice correto usando bisect_left, o alvo é inserido na lista naquela posição.

Essa abordagem garante que o processo de inserção seja eficiente, com uma complexidade de tempo de O(log n) para a busca e O(n) para a inserção devido à operação de mudança de lista. Isso é significativamente mais eficiente do que classificar a lista após cada inserção, especialmente para grandes conjuntos de dados.

exemplo de código bisect_left:

    if lo 



exemplo de código insort_left:



def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  Conclusão


O módulo bisect torna o trabalho com listas classificadas simples e eficiente. Na próxima vez que você precisar realizar uma pesquisa binária ou inserir elementos em uma lista ordenada, lembre-se do módulo bisect e economize tempo e esforço.