La búsqueda de informes de matriz “no se encuentra” aunque se encuentre

Esta es una pregunta y respuesta genérica para un error lógico que he visto en muchas preguntas de nuevos progtwigdores en una variedad de idiomas.

El problema es buscar en una matriz un elemento que coincida con algunos criterios de entrada. El algoritmo, en pseudo-código, se ve más o menos así:

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 informa “No encontrado” incluso si encuentra con éxito un elemento coincidente.

El problema es que cuando buscas algo linealmente a través de una matriz, no puedes saber que no se encuentra hasta que llegues al final de la matriz. El código en la pregunta informa “No encontrado” para cada elemento que no coincide, aunque puede haber otros elementos coincidentes.

La modificación simple es usar una variable que rastrea si encontraste algo, y luego verifica esta variable al final del ciclo.

 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 tiene un bloque else: en sus bucles for . Esto ejecuta el código solo si el ciclo se ejecuta hasta su finalización, en lugar de finalizar debido al uso de la break . Esto le permite evitar la variable found (aunque aún podría ser útil para un procesamiento posterior):

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

Algunos idiomas tienen mecanismos incorporados que se pueden usar en lugar de escribir su propio bucle.

  • Algunos lenguajes tienen una o some función que toma una función de callback, y devuelve un booleano que indica si tiene éxito para cualquier elemento de la matriz.
  • Si el idioma tiene una función de filtrado de matriz, puede filtrar la matriz de entrada con una función que verifica los criterios, y luego verificar si el resultado es una matriz vacía.
  • Si intenta hacer coincidir exactamente un elemento, la mayoría de los idiomas proporcionan una función de búsqueda o index que buscará un elemento coincidente.

Si va a realizar búsquedas frecuentes, puede ser mejor convertir la matriz en una estructura de datos que se pueda buscar de manera más eficiente. La mayoría de los lenguajes brindan estructuras de datos de hash table set y / o hash table (este último tiene muchos nombres según el idioma, por ej. Matriz asociativa, mapa, diccionario), y generalmente se pueden buscar en O (1) tiempo, mientras que el escaneo de una matriz es O (norte).