Search a 2D Matrix
Você recebe uma grade de números inteiros matrix com m linhas e n colunas, e um número inteiro target. Cada linha está ordenada em ordem crescente, e o primeiro valor de cada linha é maior que o último valor da linha acima. Retorne true se target aparecer na grade e false caso contrário, em tempo O(log(m × n)).
Função
- matrixinteger-2d-array
- a grade, fornecida como uma lista de linhas, ordenadas linha por linha
- targetinteger
- o valor a ser procurado
- Retornaboolean
- verdadeiro se o alvo estiver na grade, falso caso contrário
Restrições
1 ≤ m, n ≤ 100, ondem = matrix.lengthen = matrix[i].length- Cada linha tem o mesmo comprimento
n. -104 ≤ matrix[i][j], target ≤ 104- Cada linha está ordenada em ordem estritamente crescente, e o primeiro valor de cada linha é maior que o último valor da linha anterior.
Exemplos
- Entrada
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Saída
- true
- Explicação
- Lidos linha por linha, os 12 valores formam uma única lista ordenada. Uma busca binária nas posições de 0 a 11 verifica 21 na posição 5 (pequeno demais), 33 na posição 8 (grande demais) e, em seguida, encontra 26 na posição 6.
- Entrada
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Saída
- false
- Explicação
- 16 viria depois de 14, o último valor da linha 0, e antes de 17, o primeiro valor da linha 1. Não há nada entre eles, então 16 não está na grade.
Para ir além
Suponha que as linhas possam ter comprimentos diferentes, mas ainda estejam ordenadas de ponta a ponta. Como você converteria uma posição em uma linha e uma coluna, e qual seria o custo da busca?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Leia a matriz linha por linha, da esquerda para a direita, como se fosse uma única lista longa. O que você percebe sobre a ordem dos valores nessa lista?
As duas regras juntas significam que a matriz inteira, lida linha por linha, é uma única lista ordenada de
m × nvalores. Você pode fazer uma busca binária nela sem nunca construí-la.Faça uma busca binária nas posições de
0am × n - 1. A posiçãopfica na linhap / ne na colunap % n(divisão inteira), então cada etapa lê uma célula e descarta metade das posições restantes.
Solução
Juntas, as duas regras de ordenação fazem com que a grade, lida linha por linha, seja uma lista ordenada de m × n valores. Faça uma busca binária nessa lista por posição e converta cada posição de volta em uma linha e uma coluna com uma divisão. Uma grade de 100 por 100 precisa, então, de no máximo 14 comparações, em vez de 10000.
Verifique cada célula
Intuição
Compare cada célula com target e retorne true se houver uma correspondência, false após a última célula. Ele lê todas as células, então está correto para qualquer grade, ordenada ou não. Nunca usa a ordem, então uma grade de 100 por 100 custa até 10000 comparações.
Algoritmo
- Para cada linha de
matrix, observe cada valor em ordem. - Se o valor for igual a
target, retornetrue. - Após os loops, retorne
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseParta do canto superior direito
Intuição
A partir da célula superior direita, todo valor à esquerda é menor e todo valor abaixo é maior. Se a célula for maior que target, a coluna abaixo dela também é maior: avance para a esquerda e descarte essa coluna. Se for menor, a linha à esquerda dela também é menor: avance para baixo e descarte essa linha.
No primeiro exemplo, 14 é menor que 26, então avance para baixo até 30. 30 é maior, então avance para a esquerda até 26, que corresponde ao valor procurado. Cada passo remove uma linha ou uma coluna, então você dá no máximo m + n passos: 200 para uma grade de 100 por 100. Esse percurso só precisa que as linhas e colunas estejam ordenadas, então ignora metade do que esta grade oferece.
Algoritmo
- Comece na linha
0e na última coluna. - Enquanto a linha e a coluna estiverem dentro da grade, leia a célula.
- Se ela for igual a
target, retornetrue. - Se for maior, mova uma coluna para a esquerda; se for menor, mova uma linha para baixo.
- Quando sair da grade, retorne
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return FalseBusca binária na grade achatada
Intuição
Numere as células linha por linha: a linha 0 contém as posições de 0 a n - 1, a linha 1 contém n a 2n - 1, e assim por diante. Cada linha está ordenada e começa acima de onde a linha anterior terminou, então os valores só aumentam conforme a posição. Essa é uma lista ordenada, e a busca binária se aplica.
Você nunca constrói a lista. A posição p está na linha p / n e na coluna p % n, usando divisão inteira. No primeiro exemplo, n = 4, então a posição 6 está na linha 1, coluna 2, que contém 26. Cada comparação reduz pela metade as posições que poderiam conter target: no máximo 14 para 10000 células, com dois índices de memória extra.
Algoritmo
- Sejam
meno número de linhas e colunas, e definalo = 0,hi = m × n - 1. - Enquanto
lo ≤ hi, escolhamidno ponto médio entre eles. - Leia
value = matrix[mid / n][mid % n]. - Se
valuefor igual atarget, retornetrue. Se for menor, definalo = mid + 1; caso contrário, definahi = mid - 1. - Quando o loop terminar, retorne
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
Armadilhas e casos extremos
- Dividir pelo número de linhas em vez do número de colunas. A posição
pestá na linhap / n; usandomno lugar, o código passa em grades quadradas e falha em uma grade com 3 linhas e 4 colunas. - Na versão com duas buscas, não tratar
targetabaixo dematrix[0][0]. Nenhuma linha começa nesse valor ou abaixo dele, e um índice de linha-1chega à segunda busca. - Usar um loop com
lo < hie umhiinclusivo. Uma grade de 1 por 1 contendotargetretornafalse, porque o loop nunca é executado. - Em Lua e R, esquecer o ajuste para índices baseados em 1: a posição
pestá na linhap / n + 1, colunap % n + 1.
Perguntas frequentes3
Qual é a complexidade de tempo da busca em uma matriz 2D?
A busca binária na grade achatada é executada em tempo O(log(m × n)) e espaço O(1): no máximo 14 comparações para 10000 células. Como log(m × n) = log m + log n, ela equivale a buscar pela linha e, em seguida, dentro dela.
Você deve usar a caminhada pelo canto superior direito ou a busca binária?
A busca pelos cantos leva O(m + n) passos e só precisa que as linhas e as colunas estejam ordenadas, então também resolve a variante em que uma linha pode começar abaixo do fim da linha acima. Quando cada linha começa acima de onde a anterior termina, como aqui, a busca binária é mais rápida.
Fazer duas buscas binárias, uma para a linha e outra dentro dela, também está correto?
Sim. Faça uma busca binária na primeira coluna para encontrar a última linha cujo primeiro valor seja menor ou igual a target e, em seguida, faça uma busca binária nessa linha. Ela tem complexidade O(log m + log n), o mesmo limite. A busca única realiza o mesmo trabalho com um laço e menos casos extremos.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def searchMatrix(matrix, target):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Saída Esperada
true