A pesquisa binária divide o espaço de pesquisa pela metade em cada etapa. Em uma matriz classificada de n elementos, ele encontra um alvo em O(log n) tempo.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Simples - mas o verdadeiro poder da pesquisa binária vai muito além de arrays ordenados.
A pesquisa binária funciona sempre que você tem uma condição monotônica em um intervalo. A "matriz" nem precisa existir - você só precisa de um intervalo [lo, hi] e uma função que mude de False para True (ou vice-versa) em algum limite.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
Em vez de pesquisar em um array, pesquise no espaço de resposta. Pergunte: “Posso alcançar o resultado X?” Se sim, tente menor; se não, tente maior.
Koko tem n pilhas de bananas e h horas. Encontre a velocidade mínima de alimentação para que ela termine a tempo.
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
O espaço de resposta é [1, max(piles)] e a condição é monotônica – maior velocidade sempre significa menos horas.
Entrar participar da discussão
Uma matriz classificada girada em algum pivô: [4, 5, 6, 7, 0, 1, 2]. Metade está sempre classificada. Compare mid com lo para decidir qual metade e, em seguida, verifique se o alvo se enquadra na metade classificada.
[4, 5, 6, 7, 0, 1, 2]
L M R
Left half [4..7] is sorted.
Target 1 not in [4..7] → search right.
Em uma matriz classificada girada [3,4,5,1,2], qual metade é classificada quando mid = 2 (valor 5)?
Para encontrar a primeira ocorrência, quando você atingir o alvo, não pare - defina hi = mid e continue procurando para a esquerda. Para o último, defina lo = mid + 1 e pesquise à direita.
Este par de pesquisas também fornece a contagem de um alvo: last - first + 1.
Um elemento maior que ambos os vizinhos. Mesmo em uma matriz não classificada, a pesquisa binária funciona: se nums[mid] < nums[mid + 1], o pico está à direita; caso contrário, é para a esquerda. O(log n).
Se as linhas forem classificadas e o primeiro elemento de cada linha for maior que o último da anterior, trate a matriz como uma única matriz classificada de m × n elementos. Mapeie o índice k para a linha k // n, coluna k % n.
Encontre o maior número inteiro x onde x * x ≤ n. Espaço de pesquisa: [0, n]. Pesquisa binária clássica na resposta.
def sqrt(n):
lo, hi = 0, n
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= n:
lo = mid + 1
else:
hi = mid - 1
return hi
Problemas como "maior soma da matriz dividida" ou "capacidade de enviar pacotes em D dias" solicitam que você minimize o pior caso. A resposta é monotônica: se a capacidade C funciona, C+1 também funciona. Pesquisa binária em C.
Para 'Capacidade de envio de pacotes em dias D', qual é o espaço de busca para busca binária?
lo, hi = min_possible, max_possible
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid # mid works, try smaller
else:
lo = mid + 1 # mid fails, need larger
return lo
Ajuste hi = mid vs lo = mid dependendo se você busca o primeiro Verdadeiro ou o último Verdadeiro.
Qual é a complexidade de tempo da pesquisa binária em um espaço de resposta de tamanho S com uma verificação de viabilidade O(n)?