arrays - La búsqueda de informes de matriz "no se encuentra" aunque se encuentre

search language-agnostic

Question

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

El problema es buscar en una matriz un elemento que coincida con algunos criterios de entrada. El algoritmo, en pseudocódigo, se parece a esto:

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.

Answer 1

El problema es que cuando estás buscando algo linealmente a través de una matriz, no puedes saber que no se encuentra hasta que llegas al final de la matriz. El código en la pregunta informa "No encontrado" para cada elemento no coincidente, 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 else: bloque en sus bucles for . Esto ejecuta código solo si el ciclo se ejecuta hasta su finalización, en lugar de finalizar debido al uso de 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 idiomas tienen una función any o some que toma una función de devolución de llamada y devuelve un valor 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 verifique los criterios y luego verifique si el resultado es una matriz vacía.
• Si intenta hacer coincidir un elemento exactamente, la mayoría de los idiomas proporcionan una función de búsqueda o index que buscará un elemento coincidente.

Si va a buscar con frecuencia, puede ser mejor convertir la matriz a una estructura de datos que pueda buscarse de manera más eficiente. La mayoría de los idiomas proporcionan estructuras de datos de hash table o de set (este último tiene muchos nombres dependiendo del idioma, por ejemplo, matriz asociativa, mapa, diccionario), y estos generalmente se pueden buscar en O (1) tiempo, mientras que el escaneo de una matriz es O (norte).