A pesquisa de relatórios de matriz “não encontrados”, embora seja encontrada

Esta é uma pergunta genérica e resposta para um erro lógico que eu vi em muitas perguntas de novos programadores em uma variedade de idiomas.

O problema é procurar uma matriz por um elemento que corresponda a alguns critérios de input. O algoritmo, em pseudo-código, é algo como isto:

for each element of Array: if element matches criteria: do something with element maybe break out of loop (if only interested in first match) else: print "Not found" 

Este código relata “Não encontrado” mesmo que encontre um elemento correspondente com êxito.

O problema é que quando você está procurando por algo linearmente através de uma matriz, você não pode saber que não é encontrado até chegar ao final da matriz. O código na pergunta relata “Não encontrado” para cada elemento não correspondente, mesmo que possa haver outros elementos correspondentes.

A modificação simples é usar uma variável que rastreia se você encontrou algo e, em seguida, verifique essa variável no final do loop.

 found = false for each element of Array: if element matches criteria: do something with element found = true maybe break out of loop (if only interested in first match) if not found: print "Not found" 

Python tem um else: block em seus loops for . Isso executa o código apenas se o loop for executado até a conclusão, em vez de terminar devido ao uso de break . Isso permite que você evite a variável found (embora ainda possa ser útil para processamento posterior):

 for element in someIterable: if matchesCriteria(element): print("Found") break else: print("Not found") 

Algumas linguagens possuem mecanismos internos que podem ser usados ​​em vez de escrever seu próprio loop.

  • Algumas linguagens possuem any ou some function que recebe uma function de retorno de chamada e retorna um booleano indicando se é bem-sucedido para qualquer elemento da matriz.
  • Se o idioma tiver uma function de filtragem de matriz, você poderá filtrar a matriz de input com uma function que verifique os critérios e, em seguida, verifique se o resultado é uma matriz vazia.
  • Se você estiver tentando corresponder exatamente um elemento, a maioria dos idiomas fornece uma function de find ou index que pesquisará um elemento correspondente.

Se você pesquisar com frequência, talvez seja melhor converter a matriz em uma estrutura de dados que possa ser pesquisada com mais eficiência. A maioria das linguagens fornece estruturas de dados de set e / ou hash table (o último tem vários nomes dependendo da linguagem, por exemplo, matriz associativa, mapa, dictionary), e estes são normalmente pesquisáveis ​​em tempo O (1), enquanto a varredura de uma matriz é O (n)