Python Bisect - Pesquisa Binária

1. bisect.bisect_left() Visão geral
2. Aplicações de bisect_left()
3. bisect.bisect_right() Visão geral
4. Aplicações de bisect_right()

Neste artigo, veremos como usar os módulos integrados do Python para realizar a pesquisa binária. O módulo bisect é baseado no método da bissecção para encontrar as raízes das funções. Consiste em 6 funções: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right() que nos permite encontrar o índice de um elemento ou insira o elemento na posição correta em uma lista. Também ajuda a manter a lista classificada após cada inserção. Mas para que funcionem corretamente, temos que nos certificar de que o array já está classificado.

bisect.bisect_left() Visão geral

É usado para localizar o ponto de inserção mais à esquerda de um número x dentro de uma lista classificada. Se x já estiver presente na lista, então o novo x será inserido na posição mais à esquerda entre todos os x na lista.

Sintaxe

bisect_left(arr, x, lo=0, hi=len(a))

Parâmetros

Retornar

Ele retorna um ponto de inserção que divide a matriz em duas metades: a primeira com todos os valores menores que x e a segunda com todos os valores maiores que x.

Aplicações de bisect_left()

Encontre a primeira ocorrência de um elemento

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1


a = [1, 2, 3, 3, 3]
x = int(3)
res = binary_search(a, x)
if res == -1:
    print("Element not Found")
else:
    print("First occurrence of", x, "is at index", res)

Resultado:

First occurrence of 3 is at index 2

Encontre o maior valor menor que x

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i:
        return i - 1
    else:
        return -1


# Driver code
a = [1, 2, 4, 4, 8]
x = int(7)
res = binary_search(a, x)
if res == -1:
    print("There is no value smaller than", x)
else:
    print("Largest value smaller than", x, " is at index", res)

Resultado:

Largest value smaller than 7 is at index 3

bisect.bisect_right() Visão geral

É usado para retornar o ponto de inserção mais à direita de um número x dentro de uma lista classificada. Se x já estiver presente na lista, então o novo x será inserido na posição mais à direita entre todos os x na lista.

Sintaxe

bisect_right(arr, x, lo=0, hi=len(a))

Parâmetros

Retornar

Ele retorna um ponto de inserção que divide a matriz em duas metades: a primeira com todos os valores <= x e a segunda com todos os valores> x.

Aplicações de bisect_right()

Encontre a última ocorrência de um elemento

from bisect import bisect_right


def binary_search(a, x):
    i = bisect_right(a, x)
    if i != len(a) + 1 and a[i - 1] == x:
        return i - 1
    else:
        return -1


a = [1, 2, 4, 4]
x = int(4)
res = binary_search(a, x)
if res == -1:
    print(x, "is absent")
else:
    print("Last occurrence of", x, "is present at", res)

Resultado:

Last occurrence of 4 is present at 3