Como pesquiso um número em uma matriz 2D classificada da esquerda para a direita e de cima para baixo?

Recentemente, recebi esta pergunta da entrevista e estou curioso para saber se seria uma boa solução.

Digamos que eu receba uma matriz 2d onde todos os números na matriz estão em ordem crescente da esquerda para a direita e de cima para baixo.

Qual é a melhor maneira de pesquisar e determinar se um número de destino está na matriz?

Agora, minha primeira inclinação é utilizar uma pesquisa binária, pois meus dados são classificados. Eu posso determinar se um número está em uma única linha no tempo O (log N). No entanto, são as duas direções que me atiram.

Outra solução que pensei que poderia funcionar é começar em algum lugar no meio. Se o valor do meio é menor do que o meu alvo, então eu posso ter certeza de que ele está na porção quadrada esquerda da matriz do meio. Eu então me movo na diagonal e checo novamente, reduzindo o tamanho do quadrado que o alvo poderia estar até que eu tenha afiado o número alvo.

Alguém tem alguma boa ideia para resolver este problema?

Exemplo de array:

Classificados da esquerda para a direita, de cima para baixo.

1 2 4 5 6 2 3 5 7 8 4 6 8 9 10 5 8 9 10 11 

Aqui está uma abordagem simples:

  1. Comece no canto inferior esquerdo.
  2. Se o alvo for menor que esse valor, ele deve estar acima de nós, então suba um .
  3. Caso contrário, sabemos que o alvo não pode estar nessa coluna, então mova um deles para a direita .
  4. Vá para 2.

Para uma matriz NxM , isso é executado em O(N+M) . Eu acho que seria difícil fazer melhor. 🙂


Edit: Muita boa discussão. Eu estava falando sobre o caso geral acima; claramente, se N ou M são pequenos, você poderia usar uma abordagem de busca binária para fazer isso em algo próximo do tempo logarítmico.

Aqui estão alguns detalhes, para quem está curioso:

História

Esse algoritmo simples é chamado de pesquisa de Saddleback . Já existe há algum tempo, e é ótimo quando N == M Algumas referências:

  • David Gries, The Science of Programming . Springer-Verlag, 1989 .
  • Edsgar Dijkstra, The Saddleback Search . Nota EWD-934, 1985 .

No entanto, quando N < M , intuition sugere que a pesquisa binária deve ser capaz de ser melhor que O(N+M) : Por exemplo, quando N == 1 , uma pesquisa binária pura será executada em tempo logarítmico em vez de linear.

Limite de pior caso

Richard Bird examinou essa intuição de que a pesquisa binária poderia melhorar o algoritmo de Saddleback em um artigo de 2006:

  • Richard S. Bird, Melhorando a Pesquisa de Saddleback: Uma Lição em Design de Algoritmo , em Matemática de Construção de Programa, pp. 82--89, volume 4014, 2006 .

Usando uma técnica conversacional bastante incomum, Bird nos mostra que, para N < = M , esse problema tem um limite inferior de Ω(N * log(M/N)) . Esse limite faz sentido, pois nos dá desempenho linear quando N == M e desempenho logarítmico quando N == 1 .

Algoritmos para matrizes retangulares

Uma abordagem que usa uma pesquisa binária linha a linha é assim:

  1. Comece com uma matriz retangular onde N < M . Vamos dizer que N é linhas e M é colunas.
  2. Faça uma pesquisa binária na linha do meio por value . Se acharmos, terminamos.
  3. Caso contrário, encontramos um par adjacente de números s e g , onde s < value < g .
  4. O retângulo de números acima e à esquerda de s é menor que o value , então podemos eliminá-lo.
  5. O retângulo abaixo e à direita de g é maior que o value , então podemos eliminá-lo.
  6. Vá para o passo (2) para cada um dos dois retângulos restantes.

Em termos de complexidade de pior caso, esse algoritmo faz log(M) trabalhar para eliminar metade das soluções possíveis e, em seguida, recursivamente chama-se duas vezes em dois problemas menores. Nós temos que repetir uma versão menor desse log(M) para cada linha, mas se o número de linhas for pequeno comparado ao número de colunas, ser capaz de eliminar todas essas colunas em tempo logarítmico começa a valer a pena. .

Isto dá ao algoritmo uma complexidade de T(N,M) = log(M) + 2 * T(M/2, N/2) , que Bird mostra ser O(N * log(M/N)) .

Outra abordagem postada por Craig Gidney descreve um algoritmo similar ao da abordagem acima: ele examina uma linha por vez usando um tamanho de passo de M/N Sua análise mostra que isso resulta em desempenho O(N * log(M/N)) também.

Comparação de desempenho

A análise Big-O é muito boa, mas até que ponto essas abordagens funcionam na prática? O gráfico abaixo examina quatro algoritmos para matrizes cada vez mais "quadradas":

desempenho do algoritmo vs squareness

(O algoritmo "ingênuo" simplesmente pesquisa cada elemento da matriz. O algoritmo "recursivo" é descrito acima. O algoritmo "híbrido" é uma implementação do algoritmo de Gidney . Para cada tamanho de matriz, o desempenho foi medido pelo tempo de cada algoritmo sobre um conjunto fixo de 1.000.000 de matrizes geradas aleatoriamente.)

Alguns pontos notáveis:

  • Como esperado, os algoritmos de "pesquisa binária" oferecem o melhor desempenho em arrays retangulares e o algoritmo de Saddleback funciona melhor em matrizes quadradas.
  • O algoritmo de Saddleback tem um desempenho pior do que o algoritmo "ingênuo" para arrays de 1-d, presumivelmente porque ele faz comparações múltiplas em cada item.
  • O acerto de desempenho que os algoritmos de "pesquisa binária" assumem nos arrays quadrados é presumivelmente devido à sobrecarga de executar buscas binárias repetidas.

Resumo

O uso inteligente da pesquisa binária pode fornecer o desempenho O(N * log(M/N) para arrays retangulares e quadrados. O algoritmo "saddleback" O(N + M) é muito mais simples, mas sofre degradação de desempenho conforme as matrizes se tornam cada vez mais retangulares .

Esse problema leva Θ(b lg(t)) tempo, onde b = min(w,h) e t=b/max(w,h) . Eu discuto a solução neste post do blog .

Limite inferior

Um adversário pode forçar um algoritmo a fazer consultas Ω(b lg(t)) , restringindo-se à diagonal principal:

Adversário usando diagonal principal

Legenda: células brancas são itens menores, células cinzas são itens maiores, células amarelas são itens menores ou iguais e células laranja são itens maiores ou iguais. O adversário força a solução a ser a célula amarela ou laranja que o algoritmo consulta por último.

Observe que há listas classificadas independentes de tamanho t , exigindo que as consultas Ω(b lg(t)) sejam completamente eliminadas.

Algoritmo

  1. (Assuma sem perda de generalidade que w >= h )
  2. Compare o item de destino com a célula t à esquerda do canto superior direito da área válida
    • Se o item da célula corresponder, retorne a posição atual.
    • Se o item da célula for menor que o item de destino, elimine as células t restantes na linha com uma pesquisa binária. Se um item correspondente for encontrado ao fazer isso, retorne com sua posição.
    • Caso contrário, o item da célula é maior que o item de destino, eliminando as colunas curtas.
  3. Se não houver uma área válida, retorne a falha
  4. Ir para o passo 2

Encontrando um item:

Encontrar um item

Determinar um item não existe:

Determinar um item não existe

Legenda: os glóbulos brancos são itens menores, os glóbulos cinzentos são itens maiores e a célula verde é um item igual.

Análise

Existem b*t colunas curtas para eliminar. Existem linhas longas para eliminar. Eliminar uma linha longa custa O(lg(t)) . Eliminar t colunas curtas custa O(1) tempo.

No pior dos casos, teremos que eliminar todas as colunas e todas as linhas, tomando o tempo O(lg(t)*b + b*t*1/t) = O(b lg(t)) .

Note que estou assumindo grampos de lg para um resultado acima de 1 (ou seja, lg(x) = log_2(max(2,x)) ). É por isso que quando w=h , significando t=1 , obtemos o limite esperado de O(b lg(1)) = O(b) = O(w+h) .

Código

 public static Tuple TryFindItemInSortedMatrix(this IReadOnlyList> grid, T item, IComparer comparer = null) { if (grid == null) throw new ArgumentNullException("grid"); comparer = comparer ?? Comparer.Default; // check size var width = grid.Count; if (width == 0) return null; var height = grid[0].Count; if (height < width) { var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer); if (result == null) return null; return Tuple.Create(result.Item2, result.Item1); } // search var minCol = 0; var maxRow = height - 1; var t = height / width; while (minCol < width && maxRow >= 0) { // query the item in the minimum column, t above the maximum row var luckyRow = Math.Max(maxRow - t, 0); var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]); if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow); // did we eliminate t rows from the bottom? if (cmpItemVsLucky < 0) { maxRow = luckyRow - 1; continue; } // we eliminated most of the current minimum column // spend lg(t) time eliminating rest of column var minRowInCol = luckyRow + 1; var maxRowInCol = maxRow; while (minRowInCol <= maxRowInCol) { var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2; var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]); if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid); if (cmpItemVsMid > 0) { minRowInCol = mid + 1; } else { maxRowInCol = mid - 1; maxRow = mid - 1; } } minCol += 1; } return null; } 

Eu usaria a estratégia de divisão e conquista para esse problema, semelhante ao que você sugeriu, mas os detalhes são um pouco diferentes.

Esta será uma busca recursiva em sub-escalas da matriz.

Em cada etapa, escolha um elemento no meio do intervalo. Se o valor encontrado é o que você está procurando, então está feito.

Caso contrário, se o valor encontrado for menor que o valor que você está procurando, então você sabe que não está no quadrante acima e à esquerda de sua posição atual. Então, pesquise recursivamente os dois sub-intervalos: tudo (exclusivamente) abaixo da posição atual e tudo (exclusivamente) para a direita que está na posição atual ou acima dela.

Caso contrário, (o valor encontrado é maior que o valor que você está procurando) você sabe que não está no quadrante abaixo e à direita de sua posição atual. Então, pesquise recursivamente os dois sub-intervalos: tudo (exclusivamente) à esquerda da posição atual e tudo (exclusivamente) acima da posição atual que está na coluna atual ou uma coluna à direita.

E ba-da-bing, você achou.

Observe que cada chamada recursiva lida apenas com a subfaixa atual, não (por exemplo) TODAS as linhas acima da posição atual. Apenas aqueles no subintervalo atual.

Aqui está um pseudocódigo para você:

 bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY) if (minX == maxX and minY == maxY and arr[minX,minY] != value) return false if (arr[minX,minY] > value) return false; // Early exits if the value can't be in if (arr[maxX,maxY] < value) return false; // this subrange at all. int nextX = (minX + maxX) / 2 int nextY = (minY + maxY) / 2 if (arr[nextX,nextY] == value) { print nextX,nextY return true } else if (arr[nextX,nextY] < value) { if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY)) return true return numberSearch(arr, value, nextX + 1, maxX, minY, nextY) } else { if (numberSearch(arr, value, minX, nextX - 1, minY, maxY)) return true reutrn numberSearch(arr, value, nextX, maxX, minY, nextY) } 

As duas principais respostas dadas até agora parecem ser o discutível O(log N) “método ZigZag” e o método de pesquisa binária O(N+M) . Eu pensei em fazer alguns testes comparando os dois methods com várias configurações. Aqui estão os detalhes:

A matriz é N x N quadrados em todos os testes, com N variando de 125 a 8000 (o maior heap da minha JVM pode ser manipulado). Para cada tamanho de matriz, escolhi um local random na matriz para colocar um único 2 . Em seguida, coloquei um 3 todos os lugares possíveis (à direita e abaixo dos 2) e, em seguida, preenchi o restante da matriz com 1 . Alguns dos primeiros comentadores pareciam pensar que esse tipo de configuração geraria o pior tempo de execução para ambos os algoritmos. Para cada tamanho de matriz, selecionei 100 locais randoms diferentes para o 2 (alvo de pesquisa) e executei o teste. Eu gravei o tempo de execução médio e o tempo de execução do pior caso para cada algoritmo. Como estava ocorrendo muito rápido para obter boas leituras ms em Java e porque não confio no nanoTime () do Java, repeti cada teste 1000 vezes apenas para adicionar um fator de polarização uniforme a todos os momentos. Aqui estão os resultados:

insira a descrição da imagem aqui

O ZigZag venceu o binário em todos os testes para os tempos médios e piores, no entanto, eles estão todos dentro de uma ordem de grandeza um do outro mais ou menos.

Aqui está o código Java:

 public class SearchSortedArray2D { static boolean findZigZag(int[][] a, int t) { int i = 0; int j = a.length - 1; while (i < = a.length - 1 && j >= 0) { if (a[i][j] == t) return true; else if (a[i][j] < t) i++; else j--; } return false; } static boolean findBinarySearch(int[][] a, int t) { return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1); } static boolean findBinarySearch(int[][] a, int t, int r1, int c1, int r2, int c2) { if (r1 > r2 || c1 > c2) return false; if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false; if (a[r1][c1] > t) return false; if (a[r2][c2] < t) return false; int rm = (r1 + r2) / 2; int cm = (c1 + c2) / 2; if (a[rm][cm] == t) return true; else if (a[rm][cm] > t) { boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1); boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2); return (b1 || b2); } else { boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2); boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2); return (b1 || b2); } } static void randomizeArray(int[][] a, int N) { int ri = (int) (Math.random() * N); int rj = (int) (Math.random() * N); a[ri][rj] = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == ri && j == rj) continue; else if (i > ri || j > rj) a[i][j] = 3; else a[i][j] = 1; } } } public static void main(String[] args) { int N = 8000; int[][] a = new int[N][N]; int randoms = 100; int repeats = 1000; long start, end, duration; long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE; long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE; long zigSum = 0, zigAvg; long binSum = 0, binAvg; for (int k = 0; k < randoms; k++) { randomizeArray(a, N); start = System.currentTimeMillis(); for (int i = 0; i < repeats; i++) findZigZag(a, 2); end = System.currentTimeMillis(); duration = end - start; zigSum += duration; zigMin = Math.min(zigMin, duration); zigMax = Math.max(zigMax, duration); start = System.currentTimeMillis(); for (int i = 0; i < repeats; i++) findBinarySearch(a, 2); end = System.currentTimeMillis(); duration = end - start; binSum += duration; binMin = Math.min(binMin, duration); binMax = Math.max(binMax, duration); } zigAvg = zigSum / randoms; binAvg = binSum / randoms; System.out.println(findZigZag(a, 2) ? "Found via zigzag method. " : "ERROR. "); //System.out.println("min search time: " + zigMin + "ms"); System.out.println("max search time: " + zigMax + "ms"); System.out.println("avg search time: " + zigAvg + "ms"); System.out.println(); System.out.println(findBinarySearch(a, 2) ? "Found via binary search method. " : "ERROR. "); //System.out.println("min search time: " + binMin + "ms"); System.out.println("max search time: " + binMax + "ms"); System.out.println("avg search time: " + binAvg + "ms"); } } 

Esta é uma pequena prova do limite inferior do problema.

Você não pode fazê-lo melhor que o tempo linear (em termos de dimensões de matriz, não o número de elementos). Na matriz abaixo, cada um dos elementos marcados como * pode ser 5 ou 6 (independentemente de outros). Então, se seu valor alvo é 6 (ou 5), o algoritmo precisa examinar todos eles.

 1 2 3 4 * 2 3 4 * 7 3 4 * 7 8 4 * 7 8 9 * 7 8 9 10 

Claro que isso se expande para matrizes maiores também. Isso significa que essa resposta é ótima.

Atualização: Como apontado por Jeffrey L Whitledge, é ótimo apenas como o limite inferior assintótico em tempo de execução versus tamanho de dados de input (tratado como uma única variável). O tempo de execução tratado como function de duas variables ​​em ambas as dimensões da matriz pode ser melhorado.

Eu acho que aqui é a resposta e funciona para qualquer tipo de matriz classificada

 bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key) { if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false; if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false; if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false; if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true; int xnew = (xmin + xmax)/2; int ynew = (ymin + ymax)/2; if (arr[xnew][ynew] == key) return true; if (arr[xnew][ynew] < key) { if (findNum(arr,xnew+1,xmax,ymin,ymax,key)) return true; return (findNum(arr,xmin,xmax,ynew+1,ymax,key)); } else { if (findNum(arr,xmin,xnew-1,ymin,ymax,key)) return true; return (findNum(arr,xmin,xmax,ymin,ynew-1,key)); } } 

Pergunta interessante. Considere esta ideia – crie um limite onde todos os números sejam maiores que o seu alvo e outro onde todos os números sejam menores que o seu alvo. Se alguma coisa é deixada entre os dois, esse é o seu alvo.

Se eu estiver procurando por 3 no seu exemplo, eu leio a primeira linha até atingir 4, então, procure o menor número adjacente (incluindo diagonais) maior que 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Agora faço o mesmo para os números menores que 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Agora eu pergunto, é alguma coisa dentro dos dois limites? Se sim, deve ser 3. Se não, então não há 3. Meio indireto, já que na verdade não encontro o número, apenas deduzo que ele deve estar lá. Isto tem a vantagem adicional de contar TODOS os 3’s.

Eu tentei isso em alguns exemplos e parece funcionar bem.

A busca binária através da diagonal da matriz é a melhor opção. Podemos descobrir se o elemento é menor ou igual aos elementos na diagonal.

A. Faça uma pesquisa binária nas linhas em que o número de destino pode estar ativado.

B. Faça um gráfico: Procure o número, tomando sempre o menor nó vizinho não visitado e retrocedendo quando um número muito grande for encontrado

Pesquisa binária seria a melhor abordagem, imo. Começando em 1/2 x, 1/2 y irá cortá-lo ao meio. Ou seja, um quadrado de 5×5 seria algo como x == 2 / y = = 3. Eu arredondado um valor para baixo e um valor até melhor zona na direção do valor alvo.

Para maior clareza, a próxima iteração lhe daria algo como x == 1 / y == 2 OR x == 3 / y == 5

Bem, para começar, vamos supor que estamos usando um quadrado.

 1 2 3 2 3 4 3 4 5 

1. Procurando um quadrado

Eu usaria uma pesquisa binária na diagonal. O objective é localizar o número menor que não seja estritamente menor que o número de destino.

Digamos que eu esteja procurando por 4 por exemplo, eu acabaria localizando 5 em (2,2) .

Então, estou certo de que se 4 estiver na tabela, ele está em uma posição (x,2) ou (2,x) com x em [0,2] . Bem, isso é apenas duas pesquisas binárias.

A complexidade não é assustadora: O(log(N)) (3 buscas binárias em intervalos de comprimento N )

2. Pesquisando um retângulo, abordagem ingênua

Claro, fica um pouco mais complicado quando N e M diferem (com um retângulo), considere este caso degenerado:

 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

E digamos que eu esteja procurando por 9 … A abordagem diagonal ainda é boa, mas a definição de mudanças na diagonal. Aqui minha diagonal é [1, (5 or 6), 17] . Digamos que eu peguei [1,5,17] , então eu sei que se 9 está na tabela, está na subparte:

  5 6 7 8 6 7 8 9 10 11 12 13 14 15 16 

Isso nos dá dois retângulos:

 5 6 7 8 10 11 12 13 14 15 16 6 7 8 9 

Então podemos reciclar! provavelmente começando por aquele com menos elementos (embora neste caso nos mate).

Devo salientar que, se uma das dimensões for menor que 3 , não podemos aplicar os methods diagonais e devemos usar uma pesquisa binária. Aqui isso significaria:

  • Aplicar pesquisa binária em 10 11 12 13 14 15 16 , não encontrada
  • Aplicar pesquisa binária em 5 6 7 8 , não encontrada
  • Aplicar pesquisa binária em 6 7 8 9 , não encontrada

É complicado porque, para obter um bom desempenho, você pode querer diferenciar vários casos, dependendo da forma geral ….

3. Procurando por um retângulo, abordagem brutal

Seria muito mais fácil se nós lidássemos com um quadrado … então vamos simplificar as coisas.

 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 . . . . . . 17 . . . . . . 17 . . . . . . 17 

Nós agora temos um quadrado.

É claro que provavelmente NÃO criaremos essas linhas, poderíamos simplesmente imitá-las.

 def get(x,y): if x < N and y < M: return table[x][y] else: return table[N-1][M-1] # the max 

então ele se comporta como um quadrado sem ocupar mais memory (ao custo da velocidade, provavelmente, dependendo do cache ... oh bem: p)

EDITAR:

Eu não entendi a pergunta. Como os comentários apontam, isso só funciona no caso mais restrito.

Em uma linguagem como C, que armazena dados em ordem de linha maior, simplesmente trate-a como uma matriz 1D de tamanho n * m e use uma pesquisa binária.

Eu tenho uma solução recursiva Divide & Conquer. Idéia Básica para um passo é: Sabemos que o Left-Upper (LU) é menor e o right-bottom (RB) é o maior número, então o dado No (N) deve: N> = LU e N < = RB

IF N == LU e N == RB :::: Element Found e Abort retornando a posição / Index Se N> = LU e N < = RB = FALSE, Não não existe e aborta. Se N> = LU e N < = RB = TRUE, Divida o array 2D em 4 partes iguais de array 2D, cada um de maneira lógica. E, em seguida, aplique o mesmo passo de algoritmo a todos os quatro sub-array.

Meu Algo é correto eu tenho implementado no meu PC amigos. Complexidade: cada 4 comparações pode b usado para deduzir o total de elementos para um quarto no seu pior caso .. Então, minha complexidade passa a ser 1 + 4 x lg (n) + 4 Mas realmente esperava que isso estivesse funcionando em O n)

Eu acho que algo está errado em algum lugar no meu cálculo de complexidade, por favor, corrija se assim for ..

A solução ideal é começar no canto superior esquerdo, que tem valor mínimo. Mova-se diagonalmente para baixo, para a direita, até atingir um elemento cujo valor> = valor do elemento especificado. Se o valor do elemento for igual ao do elemento especificado, o retorno será encontrado como verdadeiro.

Caso contrário, daqui podemos proceder de duas maneiras.

Estratégia 1:

  1. Suba na coluna e pesquise pelo elemento até chegar ao fim. Se encontrado, retorno encontrado como verdadeiro
  2. Mover para a esquerda na linha e procurar o elemento dado até chegar ao fim. Se encontrado, retorno encontrado como verdadeiro
  3. retorno encontrado como falso

Estratégia 2: Deixe-me denotar o índice da linha ej denotar o índice da coluna do elemento diagonal em que paramos. (Aqui temos i = j, BTW). Deixe k = 1.

  • Repita os passos abaixo até ik> = 0
    1. Pesquise se um [ik] [j] é igual ao elemento dado. se sim, retorna encontrado como verdadeiro.
    2. Pesquise se um [i] [jk] é igual ao dado elemento. se sim, retorna encontrado como verdadeiro.
    3. Incremento k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

 public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){ // base case for recursion if(minX > maxX || minY > maxY) return false ; // early fails // array not properly intialized if(arr==null || arr.length==0) return false ; // arr[0][0]> key return false if(arr[minX][minY]>key) return false ; // arr[maxX][maxY] key ? search left quad matrix ; else { return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1)); } return false ; } 

Eu sugiro, armazene todos os personagens em uma 2D list . em seguida, localize o índice do elemento obrigatório, se existir na lista.

Se não estiver presente, imprima a mensagem apropriada e imprima linha e coluna como:

row = (index/total_columns) e column = (index%total_columns -1)

Isso implicará apenas o tempo de pesquisa binária em uma lista.

Por favor, sugira quaisquer correções. 🙂

Se a solução O (M log (N)) estiver ok para um array MxN –

 template  struct MN * get(int a[][n], int k, int M, int N){ struct MN *result = new MN; result->m = -1; result->n = -1; /* Do a binary search on each row since rows (and columns too) are sorted. */ for(int i = 0; i < M; i++){ int lo = 0; int hi = N - 1; while(lo <= hi){ int mid = lo + (hi-lo)/2; if(k < a[i][mid]) hi = mid - 1; else if (k > a[i][mid]) lo = mid + 1; else{ result->m = i; result->n = mid; return result; } } } return result; } 

Trabalhando demo C ++.

Por favor, deixe-me saber se isso não funcionaria ou se há um bug dele.

Dada uma matriz quadrada da seguinte forma:

 [abc]
 [def]
 [ijk]

Nós sabemos que um c, etc. Temos garantias apenas em uma dimensão.

Olhando para os elementos finais (c, f, k), podemos fazer um tipo de filtro: é N

Deixe-me dar um EXEMPLO onde N = j,

1) Verifique a linha 1. j

2) Verifique a linha 2. j

3) Verifique a linha 3. j

Tente novamente com N = q,

1) Verifique a linha 1. q

2) Check row 2. q < f? (no, go next)

3) Check row 3. q < k? (no, go next)

There is probably a better solution out there but this is easy to explain.. 🙂

As this is an interview question, it would seem to lead towards a discussion of Parallel programming and Map-reduce algorithms.

See http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html